Теория графов

Основные определения теории графов

• Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
• Лемма о рукопожатиях
• Теорема о существовании простого пути в случае существования пути
• Теорема о существовании простого цикла в случае существования цикла
• Матрица смежности графа
• Матрица инцидентности графа
• Циклическое пространство графа[math]^\star[/math]
• Фундаментальные циклы графа[math]^\star[/math]
• Дерево, эквивалентные определения
• Алгоритмы на деревьях[math]^\star[/math]
• Двудольные графы
• Дополнительный, самодополнительный граф
• Теоретико-множественные операции над графами[math]^\star[/math]
• Рёберное ядро
• Факторизация графов[math]^\star[/math]
• Группы графов[math]^\star[/math]
• Гиперграфы[math]^\star[/math]

Связность в графах

• Отношение связности, компоненты связности
• Отношение реберной двусвязности
• Отношение вершинной двусвязности
• Точка сочленения, эквивалентные определения
• Мост, эквивалентные определения
• Граф компонент реберной двусвязности
• Граф блоков-точек сочленения
• k-связность
• Теорема Менгера
• Теорема Менгера, альтернативное доказательство
• Вершинная, реберная связность, связь между ними и минимальной степенью вершины
• Задача о динамической связности оффлайн[math]^\star[/math]

Остовные деревья

Построение остовных деревьев

• Остовные деревья: определения, лемма о безопасном ребре
• Алгоритм Прима
• Алгоритм Краскала
• Алгоритм Борувки
• Теорема Тарьяна (критерий минимальности остовного дерева)
• Алгоритм двух китайцев
• Минимально узкое остовное дерево
• Остовное дерево в планарном графе

Свойства остовных деревьев

• Матрица Кирхгофа
• Связь матрицы Кирхгофа и матрицы инцидентности
• Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
• Количество помеченных деревьев
• Коды Прюфера

Обходы графов

• Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом

Эйлеровы графы

• Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
• Покрытие рёбер графа путями
• Алгоритм построения Эйлерова цикла
• Произвольно вычерчиваемые из заданной вершины графы
• Деревья Эйлерова обхода[math]^\star[/math]

Гамильтоновы графы

• Гамильтоновы графы
• Теорема Хватала
• Теорема Дирака
• Теорема Оре
• Теорема Поша[math]^\star[/math]
• Теорема Гуйя-Ури[math]^\star[/math]
• Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
• Теорема Гринберга[math]^\star[/math]
• Турниры
• Теорема Редеи-Камиона

Укладки графов

• Укладка графа на плоскости
• Формула Эйлера
• Непланарность [math]K_5[/math] и [math]K_{3,3}[/math]
• Укладка дерева
• Укладка графа с планарными компонентами реберной двусвязности
• Укладка графа с планарными компонентами вершинной двусвязности
• Теорема Понтрягина-Куратовского
• Теорема Вагнера
• Род, толщина, крупность, число скрещиваний[math]^\star[/math]
• Двойственный граф планарного графа
• Теорема Фари[math]^\star[/math]
• Гамма-алгоритм
• Разрез в планарных графах

Раскраски графов

• Раскраска графа
• Двудольные графы и раскраска в 2 цвета
• Хроматический многочлен
• Формула Зыкова
• Формула Уитни
• Теорема Брукса
• Верхние и нижние оценки хроматического числа[math]^\star[/math]
• Хроматическое число планарного графа
• Многочлен Татта[math]^\star[/math]
• Теория Рамсея[math]^\star[/math]
• Рёберная раскраска двудольного графа

Обход в глубину

• Обход в глубину, цвета вершин
• Лемма о белых путях
• Использование обхода в глубину для проверки связности
• Использование обхода в глубину для поиска цикла
• Использование обхода в глубину для топологической сортировки
• Использование обхода в глубину для поиска компонент сильной связности
• Использование обхода в глубину для поиска точек сочленения
• Построение компонент вершинной двусвязности
• Использование обхода в глубину для поиска мостов
• Построение компонент реберной двусвязности

Кратчайшие пути в графах

• Обход в ширину
• Алгоритм Форда-Беллмана
• Алгоритм Дейкстры
• Алгоритм Флойда
• Алгоритм Джонсона
• Алгоритм Левита[math]^\star[/math]
• Алгоритм A* [math]^\star[/math]
• Алгоритм D* [math]^\star[/math]
• Эвристики для поиска кратчайших путей[math]^\star[/math]

Задача о паросочетании

• Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
• Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
• Алгоритм Куна для поиска максимального паросочетания
• Теорема Холла
• Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
• Связь вершинного покрытия и независимого множества
• Рёберное ядро[math]^\star[/math]
• Матрица Татта и связь с размером максимального паросочетания в двудольном графе
• Теорема Татта о существовании полного паросочетания
• Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
• Декомпозиция Эдмондса-Галлаи
• Задача об устойчивом паросочетании[math]^\star[/math]
• Совершенное паросочетание в кубическом графе[math]^\star[/math]

Задача о максимальном потоке

• Определение сети, потока
• Разрез, лемма о потоке через разрез
• Дополняющая сеть, дополняющий путь
• Сложение и разность потоков
• Теорема Форда-Фалкерсона
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алоритм Эдмондса-Карпа
• Алгоритм масштабирования потока
• Блокирующий поток
• Схема алгоритма Диница
• Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
• Алгоритм Голдберга-Тарьяна[math]^\star[/math]
• Алгоритм поиска блокирующего потока в ациклической сети
• Метод проталкивания предпотока
• Алгоритм "поднять-в-начало"
• Теорема о декомпозиции
• Теорема о декомпозиционном барьере
• Циркуляция потока
• Алгоритм Штор-Вагнера нахождения минимального разреза
• Алгоритм Каргера для нахождения минимального разреза[math]^\star[/math]
• Примеры сведения к задачам поиска потока

Задача о потоке минимальной стоимости

• Поток минимальной стоимости
• Теорема Форда-Фалкерсона о потоке минимальной стоимости
• Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
• Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
• Использование потенциалов Джонсона при поиске потока минимальной стоимости
• Сведение задачи о назначениях к задаче о потоке минимальной стоимости
• Венгерский алгоритм решения задачи о назначениях
• Алгоритм отмены цикла минимального среднего веса[math]^\star[/math]