Полное название: Дискретная математика — графы, матроиды, алгоритмы
Описание материала:
1. Основные понятия теории графов
Основные определения
Маршруты, связность, циклы и разрезы
Ориентированные графы
Матрицы, ассоциированные с графом
2. Деревья
Леса, деревья, остовы
Блоки и точки сочленения
Число остовов в связном обыкновенном графе
3. Обходы графов
Эйлеровы графы
Гамильтоновы графы
4. Матроиды
Полумодулярные решетки, условие Жордана—Дедекинда
Конечномерные геометрические решетки и матроиды
Основные понятия теории матроидов
Различные аксиоматизации матроидов
Двойственный матроид
Жадный алгоритм
Изоморфизмы матроидов
Пространство циклов бинарного матроида
Пространство циклов и пространство разрезов графа
Монотонные полумодулярные функции. Индуцированный матроид
Трансверсальные матроиды
Дизъюнктное объединение и сумма матроидов
5. Планарность
Укладки графов, планарные графы
Формула Эйлера для плоских графов
Критерий планарности графа
Двойственные графы
6. Раскраски
Хроматические числа
Хроматические многочлены
Коэффициенты хроматических многочленов
7. Введение в алгоритмы
Алгоритмы и их сложность
Запись алгоритмов
Корневые и бинарные деревья
Сортировка массивов
8. Поиск в графе
Поиск в глубину
Алгоритм отыскания блоков и точек сочленения
Алгоритм отыскания компонент сильной связности в орграфе
Поиск в ширину
Алгоритм отыскания эйлеровой цепи в эйлеровом графе
9. Задача о минимальном остове
10. Пути в сетях
Постановка задачи
Общий случай. Алгоритм Форда—Беллмана
Cлучай неотрицательных весов. Алгоритм Дейкcтры
Случай бесконтурной сети
Задача о максимальном пути и сетевые графики
Задача о maxmin-пути
Задача о кратчайших путях между всеми парами вершин
11. Задача о максимальном потоке
Основные понятия и результаты
Алгоритм Форда—Фалкерсона
12. Паросочетания в двудольных графах
Основные понятия
Задача о наибольшем паросочетании. Алгоритм Хопкрофта—Карпа
Задача о полном паросочетании. Алгоритм Куна
Задача о назначениях. Венгерский алгоритм
13. Задача коммивояжера
Основные понятия
Алгоритм отыскания гамильтоновых циклов
Алгоритмы решения задачи коммивояжера с гарантированной оценкой точности
Решение задачи коммивояжера методом ветвей и границ