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

2017-11-16T18:09:23Z

5.18.243.24: /* Обходы графов */

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

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

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

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

== Обходы графов ==
* [[Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом]]
=== Эйлеровы графы ===
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие рёбер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Деревья Эйлерова обхода]]<tex>^\star</tex>

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

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

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

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

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

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

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

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

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория графов]]

Викиконспекты - Вклад участника [ru]

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