|
01. Теоретико-множественное введение
|
|
02. Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и инциденций. Изоморфизм графов
|
|
03. Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра, подразбиения ребра. Дерево и его особенности
|
|
04. Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей
|
|
05. Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла
|
|
06. Формулировка теоремы Менгера (вершинный и реберный варианты), теорема Холла о системах различных представителей и теорема Кёнига о независимых клетках в матрице
|
|
07. Определение паросочений в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе. Решение задачи о назначениях на узкие места
|
|
08. Цепи и антицепи в частично-упорядоченном множестве. Теорема Дилворта. Алгоритм разбиения частично-упорядоченного множества на минимальное число цепей
|
|
09. Планарные и плоские графы. Формулировки теоремы Понтрягина-Куратовского и теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа
|
|
10. Раскраска графа. Формулировка теоремы о пяти красках. Хроматическое число и алгоритм Зыкова вычисления хроматического многочлена графа
|
|
11. Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда постро-ения кратчайших маршрутов
|
|
12. Остов в графе и алгоритм Краскала поиска остова минимального веса во взвешенном графе
|
|
13. Ориентированный граф и его графическая интерпретация. Локальные степени. Мат-рица смежностей. Ориентированные пути и связность в ориентированном графе
|
|
14. Сети и потоки в сетях. Стационарные потоки. Алгоритм Форда-Фалкерсона поиска максимального стационарного потока
|
|
15. Перестановки, размещения и сочетания. Бином Ньютона и иллюстративные примеры
|
|
16. Метод включения-исключения перечисления элементов множества, не обладающих заданными свойствами. Задача о беспорядках и задача о встречах
|
|
17. Формальные степенные ряды и действия над ними. Производящие функции последова-тельностей
|
|
18. Линейные рекуррентные соотношения и их решение с помощью поизводящих функций. Числа Фиббоначчи
|
