1679
правок
Изменения
→11. Задача о максимальном потоке
== 11. Задача о максимальном потоке ==
# [[Определение сети, потока]]
## ссылки на русскую и английскую википедию
# [[Разрез, лемма о потоке через разрез]]
## англоязычные термины
## добавить определение минимального разреза
## ссылки на русскую и английскую википедию
# [[Дополняющая сеть, дополняющий путь]]
## Дополняющую сеть также называют остаточной, указать это
## ссылки на русскую и английскую википедию
# [[Лемма о сложении потоков]]
## добавить внутренних ссылок
# [[Теорема Форда-Фалкерсона]]
# [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
## гм, и зачем "дельта" русским словом в псевдокоде?
## псевдокод сейчас не вполне понятен — какой-то Cmin, какой-то dfs, который непонятно как использовать. Обернуть это в полноценную функцию, которая считает значение потока.
# [[Алоритм Эдмондса-Карпа]]
## а описание алгоритма где?
## везде упоминается кратчайший путь, но не указывается, какой конкретно — по ребрам, пропускным способностям, или чему?
## ссылки на русскую/английскую википедию
# [[Алгоритм масштабирования потока]]
## ссылки на русскую/английскую википедию
## ссылка на "Андрей Станкевич: Задача о максимальном потоке" на работает, а жаль, интересно даже, что там было. Если есть, найдите другой источник этой же статьи.
# [[Блокирующий поток]]
## англоязычные термины
## ссылки на русскую и английскую википедию
# [[Схема алгоритма Диница]]
# [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
