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