Теория графов:Тикеты — различия между версиями
(→11. Задача о потоке минимальной стоимости) |
м |
||
| Строка 1: | Строка 1: | ||
| + | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7) | ||
| − | == | + | == 1. Остовные деревья == |
=== Построение остовных деревьев === | === Построение остовных деревьев === | ||
<ol> | <ol> | ||
| Строка 23: | Строка 24: | ||
== Обходы графов == | == Обходы графов == | ||
| − | === Эйлеровы графы === | + | === 2 Эйлеровы графы === |
# [[Алгоритм построения Эйлерова цикла]] (2) | # [[Алгоритм построения Эйлерова цикла]] (2) | ||
## Какое-то мутное доказательство леммы про корректность алгоритма | ## Какое-то мутное доказательство леммы про корректность алгоритма | ||
| − | === Гамильтовы графы === | + | === 3 Гамильтовы графы === |
<ol value="2"> | <ol value="2"> | ||
<li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li> | <li> [[Алгоритм нахождения Гамильтонова цикла в условиях теорем Дирака и Оре]] </li> | ||
</ol> | </ol> | ||
| − | == | + | == 4. Обход в глубину == |
# [[Обход в глубину, цвета вершин]] | # [[Обход в глубину, цвета вершин]] | ||
# [[Лемма о белых путях]] | # [[Лемма о белых путях]] | ||
| Строка 45: | Строка 46: | ||
# [[Построение компонент реберной двусвязности]] | # [[Построение компонент реберной двусвязности]] | ||
| − | == | + | == 5. Кратчайшие пути в графах == |
# [[Обход в ширину]] | # [[Обход в ширину]] | ||
# [[Алгоритм Форда-Беллмана]] | # [[Алгоритм Форда-Беллмана]] | ||
| Строка 56: | Строка 57: | ||
# [[Эвристики для поиска кратчайших путей]] | # [[Эвристики для поиска кратчайших путей]] | ||
| − | == | + | == 6. Задача о паросочетании == |
# [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | # [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]] | ||
# [[Алгоритм Куна для поиска максимального паросочетания]] | # [[Алгоритм Куна для поиска максимального паросочетания]] | ||
| Строка 62: | Строка 63: | ||
## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ## как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками | ||
| − | == | + | == 7. Задача о максимальном потоке == |
# [[Определение сети, потока]] | # [[Определение сети, потока]] | ||
# [[Разрез, лемма о потоке через разрез]] | # [[Разрез, лемма о потоке через разрез]] | ||
| Строка 91: | Строка 92: | ||
# [[Алгоритм Каргера для нахождения минимального разреза]] | # [[Алгоритм Каргера для нахождения минимального разреза]] | ||
| − | == | + | == 8. Задача о потоке минимальной стоимости == |
# [[Поток минимальной стоимости]] | # [[Поток минимальной стоимости]] | ||
# [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | # [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]] | ||
Версия 22:59, 22 сентября 2017
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела (например, конспект Алгоритм A* из раздела Кратчайшие пути в графах имеет тикет 5-7)
Содержание
1. Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев (7)
- Англоязычные термины оформить правильно
- Добавить определение покрывающего дерева
- Описать реализацию красиво
- Дефис заменить на тире
- Отформатировать псевдокод
- Доказать, почему не более V конденсаций
- Источники информации оформить правильно
- Доказать второе замечание
- Добавить отступы в описании примера
- 5ый пункт в описании алгоритма расписать чуть понятней
- Категория
Обходы графов
2 Эйлеровы графы
- Алгоритм построения Эйлерова цикла (2)
- Какое-то мутное доказательство леммы про корректность алгоритма
3 Гамильтовы графы
4. Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
5. Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
6. Задача о паросочетании
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
- как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
7. Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа (0,25)
- Добавить см также
- Алгоритм масштабирования потока
- Блокирующий поток (0,5)
- Добавить немного общей информации
- Интервики
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм поиска блокирующего потока в ациклической сети (10)
- алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
- Метод проталкивания предпотока (7)
- Картиночки с резервуарами!
- Источники информации
- Добавить см. также
- Дефисы заменить на тире
- Отформатировать псевдокоды
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Каргера для нахождения минимального разреза
8. Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
- Написать и оформить так, чтобы не было чуши
- Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0,5)
- Добавить см также
- Источники информации оформить нормально
- Венгерский алгоритм решения задачи о назначениях
