Дискретная математика. Графы

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