Теория графов — различия между версиями
Vitalik (обсуждение | вклад) (→Задача о максимальном потоке: +1) |
м (rollbackEdits.php mass rollback) |
||
| (не показана 21 промежуточная версия 17 участников) | |||
| Строка 17: | Строка 17: | ||
* [[Группы графов]]<tex>^\star</tex> | * [[Группы графов]]<tex>^\star</tex> | ||
* [[Гиперграфы]]<tex>^\star</tex> | * [[Гиперграфы]]<tex>^\star</tex> | ||
| + | * [[Алгебра графов]]<tex>^\star</tex> | ||
| + | * [[Барицентр дерева]] | ||
== Связность в графах == | == Связность в графах == | ||
| Строка 31: | Строка 33: | ||
* [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | * [[Вершинная, реберная связность, связь между ними и минимальной степенью вершины]] | ||
* [[Задача о динамической связности оффлайн]]<tex>^\star</tex> | * [[Задача о динамической связности оффлайн]]<tex>^\star</tex> | ||
| + | * [[Задача о динамической связности]] | ||
== Остовные деревья == | == Остовные деревья == | ||
| Строка 42: | Строка 45: | ||
* [[Минимально узкое остовное дерево]] | * [[Минимально узкое остовное дерево]] | ||
* [[Остовное дерево в планарном графе]] | * [[Остовное дерево в планарном графе]] | ||
| + | * [[Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами]] | ||
=== Свойства остовных деревьев === | === Свойства остовных деревьев === | ||
| Строка 51: | Строка 55: | ||
== Обходы графов == | == Обходы графов == | ||
| + | * [[Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом]] | ||
=== Эйлеровы графы === | === Эйлеровы графы === | ||
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | * [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]] | ||
| Строка 56: | Строка 61: | ||
* [[Алгоритм построения Эйлерова цикла]] | * [[Алгоритм построения Эйлерова цикла]] | ||
* [[Произвольно вычерчиваемые из заданной вершины графы]] | * [[Произвольно вычерчиваемые из заданной вершины графы]] | ||
| + | * [[Графы де Брюина]] | ||
* [[Деревья Эйлерова обхода]]<tex>^\star</tex> | * [[Деревья Эйлерова обхода]]<tex>^\star</tex> | ||
| Строка 92: | Строка 98: | ||
* [[Формула Уитни]] | * [[Формула Уитни]] | ||
* [[Теорема Брукса]] | * [[Теорема Брукса]] | ||
| + | * [[Хроматическое число планарного графа]] | ||
* [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex> | * [[Верхние и нижние оценки хроматического числа]]<tex>^\star</tex> | ||
| − | * [[ | + | * [[Проблема четырех красок]]<tex>^\star</tex> |
* [[Многочлен Татта]]<tex>^\star</tex> | * [[Многочлен Татта]]<tex>^\star</tex> | ||
* [[Теория Рамсея]]<tex>^\star</tex> | * [[Теория Рамсея]]<tex>^\star</tex> | ||
| + | * [[Рёберная раскраска двудольного графа]] | ||
| + | * [[Теорема Турана об экстремальном графе]] | ||
| + | * [[Гипотеза Хивуда]] | ||
== Обход в глубину == | == Обход в глубину == | ||
| Строка 131: | Строка 141: | ||
* [[Теорема Татта о существовании полного паросочетания]] | * [[Теорема Татта о существовании полного паросочетания]] | ||
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | * [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]] | ||
| − | * [[Декомпозиция Эдмондса-Галлаи]] | + | * [[Декомпозиция Эдмондса-Галлаи | Декомпозиция Эдмондса-Галлаи. Формула Бержа]] |
| + | * [[Лапы и минимальные по включению барьеры в графе]] | ||
| + | * [[Пересечение всех максимальных по включению барьеров]] | ||
* [[Задача об устойчивом паросочетании]]<tex>^\star</tex> | * [[Задача об устойчивом паросочетании]]<tex>^\star</tex> | ||
* [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex> | * [[Совершенное паросочетание в кубическом графе]]<tex>^\star</tex> | ||
| + | * [[Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр]] | ||
| + | * [[Теорема Самнера — Лас Вергнаса]] | ||
== Задача о максимальном потоке == | == Задача о максимальном потоке == | ||
| Строка 167: | Строка 181: | ||
* [[Венгерский алгоритм решения задачи о назначениях]] | * [[Венгерский алгоритм решения задачи о назначениях]] | ||
* [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex> | * [[Алгоритм отмены цикла минимального среднего веса]]<tex>^\star</tex> | ||
| + | |||
| + | == Случайные графы == | ||
| + | * [[Случайные графы|Введение: определения, наличие треугольников, связность, диаметр два]] | ||
| + | * [[Теорема о гигантской компоненте. Поиск в ширину в случайном графе|Теорема о гигантской компоненте. Поиск в ширину в случайном графе]] | ||
| + | * [[Теорема о существовании порога для монотонных свойств | Теорема о существовании порога для монотонных свойств]] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Теория графов]] | [[Категория: Теория графов]] | ||
Текущая версия на 19:34, 4 сентября 2022
Содержание
Основные определения теории графов
- Основные определения: граф, ребро, вершина, степень, петля, путь, цикл
- Лемма о рукопожатиях
- Теорема о существовании простого пути в случае существования пути
- Теорема о существовании простого цикла в случае существования цикла
- Матрица смежности графа
- Матрица инцидентности графа
- Циклическое пространство графа
- Фундаментальные циклы графа
- Дерево, эквивалентные определения
- Алгоритмы на деревьях
- Двудольные графы
- Дополнительный, самодополнительный граф
- Теоретико-множественные операции над графами
- Рёберное ядро
- Факторизация графов
- Группы графов
- Гиперграфы
- Алгебра графов
- Барицентр дерева
Связность в графах
- Отношение связности, компоненты связности
- Отношение реберной двусвязности
- Отношение вершинной двусвязности
- Точка сочленения, эквивалентные определения
- Мост, эквивалентные определения
- Граф компонент реберной двусвязности
- Граф блоков-точек сочленения
- k-связность
- Теорема Менгера
- Теорема Менгера, альтернативное доказательство
- Вершинная, реберная связность, связь между ними и минимальной степенью вершины
- Задача о динамической связности оффлайн
- Задача о динамической связности
Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев
- Минимально узкое остовное дерево
- Остовное дерево в планарном графе
- Максимальное количество попарно непересекающихся остовных деревьев в графе с n вершинами
Свойства остовных деревьев
- Матрица Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Количество помеченных деревьев
- Коды Прюфера
Обходы графов
Эйлеровы графы
- Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов
- Покрытие рёбер графа путями
- Алгоритм построения Эйлерова цикла
- Произвольно вычерчиваемые из заданной вершины графы
- Графы де Брюина
- Деревья Эйлерова обхода
Гамильтоновы графы
- Гамильтоновы графы
- Теорема Хватала
- Теорема Дирака
- Теорема Оре
- Теорема Поша
- Теорема Гуйя-Ури
- Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре
- Теорема Гринберга
- Турниры
- Теорема Редеи-Камиона
Укладки графов
- Укладка графа на плоскости
- Формула Эйлера
- Непланарность и
- Укладка дерева
- Укладка графа с планарными компонентами реберной двусвязности
- Укладка графа с планарными компонентами вершинной двусвязности
- Теорема Понтрягина-Куратовского
- Теорема Вагнера
- Род, толщина, крупность, число скрещиваний
- Двойственный граф планарного графа
- Теорема Фари
- Гамма-алгоритм
- Разрез в планарных графах
Раскраски графов
- Раскраска графа
- Двудольные графы и раскраска в 2 цвета
- Хроматический многочлен
- Формула Зыкова
- Формула Уитни
- Теорема Брукса
- Хроматическое число планарного графа
- Верхние и нижние оценки хроматического числа
- Проблема четырех красок
- Многочлен Татта
- Теория Рамсея
- Рёберная раскраска двудольного графа
- Теорема Турана об экстремальном графе
- Гипотеза Хивуда
Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
Задача о паросочетании
- Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Теорема Холла
- Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
- Связь вершинного покрытия и независимого множества
- Рёберное ядро
- Матрица Татта и связь с размером максимального паросочетания в двудольном графе
- Теорема Татта о существовании полного паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий
- Декомпозиция Эдмондса-Галлаи. Формула Бержа
- Лапы и минимальные по включению барьеры в графе
- Пересечение всех максимальных по включению барьеров
- Задача об устойчивом паросочетании
- Совершенное паросочетание в кубическом графе
- Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр
- Теорема Самнера — Лас Вергнаса
Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Сложение и разность потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа
- Алгоритм масштабирования потока
- Блокирующий поток
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм Голдберга-Тарьяна
- Алгоритм поиска блокирующего потока в ациклической сети
- Метод проталкивания предпотока
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Штор-Вагнера нахождения минимального разреза
- Алгоритм Каргера для нахождения минимального разреза
- Примеры сведения к задачам поиска потока
Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости
- Венгерский алгоритм решения задачи о назначениях
- Алгоритм отмены цикла минимального среднего веса
