Графы и их применения — различия между версиями
DanilovB (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | + | Обязательный курс магистерской программы "Дискретные структуры и алгоритмы" | |
| + | |||
| + | Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров | ||
| + | |||
| + | Лектор — доцент [[Селезнева Светлана Николаевна]] | ||
| + | |||
| + | ==Программа курса== | ||
| + | |||
| + | '''Лекция 1'''. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев. | ||
| + | |||
| + | '''Лекция 2'''. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин. | ||
| − | |||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] | ||
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | ||
Версия 12:52, 8 сентября 2015
Обязательный курс магистерской программы "Дискретные структуры и алгоритмы"
Курс читается в 1-м семестре магистратуры, 2 ч лекций, 1 ч семинаров
Лектор — доцент Селезнева Светлана Николаевна
Программа курса
Лекция 1. Основные определения. Простейшие свойства графов. Граф, изоморфизм графов. Степень вершины, изолированная и висячая вершины. Теорема о сумме степеней вершин графа. Маршрут, путь, цикл в графе. Теорема о свойствах путей и циклов в графе. Связность, компонента связности. Теорема о числе ребер в связном графе. Дерево. Теоремы о свойствах деревьев.
Лекция 2. Остовное дерево. Алгоритмы построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях связного графа. Теоремы об оценке числа висячих вершин остовного дерева связного графа. Труднорешаемые задачи, труднорешаемость задачи построения остовного дерева с наибольшим числом висячих вершин.
