748
правок
Изменения
→10. Задача о максимальном потоке
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
# '''взяли''' [[Алоритм Эдмондса-Карпа]] (50,25)## Полностью описать пример про грибок с картинками в конспектеДобавить см также
# [[Алгоритм масштабирования потока]]
# ''взяли'' [[Блокирующий поток]] (10,5)## англоязычные термины## ссылки на русскую и английскую википедию
## Добавить немного общей информации
## Расположить красиво картинки, чтобы не наезжалиИнтервики
# [[Схема алгоритма Диница]]
# '''fixed''' [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]] (6)## может, назвать остаточную сеть <tex>G_f</tex>, как в предыдущих конспектах?## "сети с текущим потоком, равным 0, и максимальным потоком, равным F" — в какой сети? (бывает исходная, остаточная и слоистая еще как минимум) Тут имеется в виду, что расстояние измерили до того, как пускать поток, что ли?## В лемме в утверждении фигурирует поток <tex>f</tex>, но дальше про него ничего нет. Зачем он?## "Мы можем применить Лемму(2" — лемму 3, наверное?## Дефисы на тире## Знаки неравенств## Источники информации# [[Алгоритм поиска блокирующего потока в ациклической сети]](10)## '''!!! (10)''' алгоритм МКМ плохо и непонятно написан, желательно переписать описание, сделать псевдокод чуть менее абстрактным, добавить доказательство, добавить картиночку, вынести в отдельную статью, ссылка на оригинальную статью есть в обсуждении# '''!!!''' [[Метод проталкивания предпотока]] (7)
## Картиночки с резервуарами!
## Источники информации
# [[Алгоритм "поднять-в-начало"]]
# [[Теорема о декомпозиции]]
# ''fixed'' [[Теорема о декомпозиционном барьере]] (3)## Источники информации## Пояснить,почему такие константы используются## Увеличить дроби## А что из этой теоремы следует?
# [[Циркуляция потока]]
# [[Алгоритм Каргера для нахождения минимального разреза]]
