Теория графов
Содержание
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
- Алгоритмы на деревьях
- Двудольные графы
- Дополнительный, самодополнительный граф
- Теоретико-множественные операции над графами
- Рёберное ядро
- Факторизация графов
- Группы графов
- Гиперграфы
- Алгебра графов
- Барицентр дерева
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
- Задача о динамической связности оффлайн
- Задача о динамической связности
Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
- Минимально узкое остовное дерево
- Остовное дерево в планарном графе
- Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие рёбер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Графы де Брюина
- Деревья Эйлерова обхода
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Теорема Гринберга
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Теорема Вагнера
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
- Разрез в планарных графах
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Хроматическое число планарного графа
- Верхние и нижние оценки хроматического числа
- Проблема четырех красок
- Многочлен Татта
- Теория Рамсея
- Рёберная раскраска двудольного графа
- Теорема Турана об экстремальном графе
- Гипотеза Хивуда
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
Задача о паросочетании
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Рёберное ядро
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
- Декомпозиция Эдмондса-Галлаи
- Лапы и минимальные по включению барьеры в графе
- Пересечение всех максимальных по включению барьеров
- Задача об устойчивом паросочетании
- Совершенное паросочетание в кубическом графе
- Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр
- Теорема Самнера — Лас Вергнаса
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Сложение и разность потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Алгоритм масштабирования потока
- Блокирующий поток
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм Голдберга-Тарьяна
- Алгоритм поиска блокирующего потока в ациклической сети
- Метод проталкивания предпотока
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Штор-Вагнера нахождения минимального разреза
- Алгоритм Каргера для нахождения минимального разреза
- Примеры сведения к задачам поиска потока
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
- Алгоритм отмены цикла минимального среднего веса
