Теория графов:Тикеты — различия между версиями
(→Эйлеровы графы) |
(→10. Задача о максимальном потоке) |
||
| Строка 69: | Строка 69: | ||
# [[Теорема Форда-Фалкерсона]] | # [[Теорема Форда-Фалкерсона]] | ||
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | # [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]] | ||
| − | # | + | # [[Алоритм Эдмондса-Карпа]] (0,25) |
| − | ## | + | ## Добавить см также |
# [[Алгоритм масштабирования потока]] | # [[Алгоритм масштабирования потока]] | ||
| − | # | + | # [[Блокирующий поток]] (0,5) |
| − | |||
| − | |||
## Добавить немного общей информации | ## Добавить немного общей информации | ||
| − | ## | + | ## Интервики |
# [[Схема алгоритма Диница]] | # [[Схема алгоритма Диница]] | ||
| − | # | + | # [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] |
| − | + | # [[Алгоритм поиска блокирующего потока в ациклической сети]] (10) | |
| − | + | ## алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении | |
| − | + | # [[Метод проталкивания предпотока]] (7) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Алгоритм поиска блокирующего потока в ациклической сети]] | ||
| − | ## | ||
| − | # | ||
## Картиночки с резервуарами! | ## Картиночки с резервуарами! | ||
## Источники информации | ## Источники информации | ||
| Строка 96: | Строка 87: | ||
# [[Алгоритм "поднять-в-начало"]] | # [[Алгоритм "поднять-в-начало"]] | ||
# [[Теорема о декомпозиции]] | # [[Теорема о декомпозиции]] | ||
| − | # | + | # [[Теорема о декомпозиционном барьере]] |
| − | |||
| − | |||
| − | |||
| − | |||
# [[Циркуляция потока]] | # [[Циркуляция потока]] | ||
# [[Алгоритм Каргера для нахождения минимального разреза]] | # [[Алгоритм Каргера для нахождения минимального разреза]] | ||
Версия 22:21, 22 сентября 2017
Содержание
3. Остовные деревья
Построение остовных деревьев
- Остовные деревья: определения, лемма о безопасном ребре
- Алгоритм Прима
- Алгоритм Краскала
- Алгоритм Борувки
- Теорема Тарьяна (критерий минимальности остовного дерева)
- Алгоритм двух китайцев (7)
- Англоязычные термины оформить правильно
- Добавить определение покрывающего дерева
- Описать реализацию красиво
- Дефис заменить на тире
- Отформатировать псевдокод
- Доказать, почему не более V конденсаций
- Источники информации оформить правильно
- Доказать второе замечание
- Добавить отступы в описании примера
- 5ый пункт в описании алгоритма расписать чуть понятней
- Категория
Обходы графов
Эйлеровы графы
- Алгоритм построения Эйлерова цикла (2)
- Какое-то мутное доказательство леммы про корректность алгоритма
Гамильтовы графы
7. Обход в глубину
- Обход в глубину, цвета вершин
- Лемма о белых путях
- Использование обхода в глубину для проверки связности
- Использование обхода в глубину для поиска цикла в ориентированном графе
- Использование обхода в глубину для топологической сортировки
- Использование обхода в глубину для поиска компонент сильной связности
- Использование обхода в глубину для поиска точек сочленения
- Построение компонент вершинной двусвязности
- Использование обхода в глубину для поиска мостов
- Построение компонент реберной двусвязности
8. Кратчайшие пути в графах
- Обход в ширину
- Алгоритм Форда-Беллмана
- Алгоритм Дейкстры
- Алгоритм Флойда
- Алгоритм Джонсона
- Алгоритм Левита
- Алгоритм A*
- Алгоритм D*
- Эвристики для поиска кратчайших путей
9. Задача о паросочетании
- Алгоритм Форда-Фалкерсона для поиска максимального паросочетания
- Алгоритм Куна для поиска максимального паросочетания
- Паросочетания в недвудольных графах. Алгоритм вырезания соцветий (7)
- как-то тут сумбурно написано и все в кучу, надо это аккуратно расписать, выделить алгоритм, доказательство и привести пример с картинками
10. Задача о максимальном потоке
- Определение сети, потока
- Разрез, лемма о потоке через разрез
- Дополняющая сеть, дополняющий путь
- Лемма о сложении потоков
- Теорема Форда-Фалкерсона
- Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
- Алоритм Эдмондса-Карпа (0,25)
- Добавить см также
- Алгоритм масштабирования потока
- Блокирующий поток (0,5)
- Добавить немного общей информации
- Интервики
- Схема алгоритма Диница
- Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями
- Алгоритм поиска блокирующего потока в ациклической сети (10)
- алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении
- Метод проталкивания предпотока (7)
- Картиночки с резервуарами!
- Источники информации
- Добавить см. также
- Дефисы заменить на тире
- Отформатировать псевдокоды
- Алгоритм "поднять-в-начало"
- Теорема о декомпозиции
- Теорема о декомпозиционном барьере
- Циркуляция потока
- Алгоритм Каргера для нахождения минимального разреза
11. Задача о потоке минимальной стоимости
- Поток минимальной стоимости
- Теорема Форда-Фалкерсона о потоке минимальной стоимости
- fixed Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети (0.5)
- Интервики на декомпозицию
- Знаки неравенств
- Источники информации
- Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости
- !!! Использование потенциалов Джонсона при поиске потока минимальной стоимости (5)
- Написать и оформить так, чтобы не было чуши
- взяли Сведение задачи о назначениях к задаче о потоке минимальной стоимости (0.5)
- Взять задачи в шаблон
- Оформить покрасивей и правильней
- Венгерский алгоритм решения задачи о назначениях
