Носырева Л.Л. Дискретная математика. Графы

Конспективный материал к лекциям. Иркутский государственный технический университет.
2006г.
Введение.

Определения графов.
История теории графов.
Основное определение.
Виды графов.
Изоморфизм графов.
Элементы графов.
Операции над графами.
Представление графов в ЭВМ.
Теорема Менгера.
Теорема Холла.
Потоки в сетях.
Теорема Форда и Фалкерсона.
Алгоритм нахождения максимального потока.
Связность в орграфах.
Кратчайшие пути.
Алгоритм Флойда.
Алгоритм Дейкстры.
Деревья.
Свободные деревья.
Основные свойства деревьев.
Ориентированные, упорядоченные и бинарные деревья.
Представление деревьев в ЭВМ.
Алгоритм симметричного обхода бинарного дерева.
Деревья сортировки.
Алгоритм бинарного (двоичного) поиска.
Алгоритм поиска в дереве сортировки.
Алгоритм вставки в дерево сортировки.
Алгоритм удаления из дерева сортировки.
Вспомогательные алгоритмы для дерева сортировки.
Выровненные деревья.
Сбалансированные деревья.
Кратчайший остов.
Схема алгоритма построения кратчайшего остова.
Алгоритм Краскала.
Циклы.
Фундаментальные циклы и разрезы.
Эйлеровы циклы.
Эйлеровы графы.
Алгоритм построения эйлерова цикла в эйлеровом графе.
Гамильтоновы циклы.
Гамильтоновы графы.
Задача коммивояжера.
Независимость и покрытия.
Построение независимых множеств вершин.
Постановка задачи отыскания наибольшего независимого множества вершин
Поиск с возвратами
Улучшенный перебор
Алгоритм построения максимальных независимых множеств вершин
Доминирующие множества
Задача о наименьшем покрытии
Эквивалентные формулировки ЗНП
Связь ЗНП с другими задачами
Раскраска графов
Хроматическое число
Планарност
Теорема о пяти красках
Алгоритмы раскрашивания
Точный алгоритм раскрашивания
Приближенный алгоритм последовательного раскрашивания
Улучшенный алгоритм последовательного раскрашивания