3622
правки
Изменения
м
Нет описания правки
Теперь докажем саму теорему:
* Максимальный поток по модулю равен потоку через разрез, который разделяет <tex>A</tex> и <tex>B</tex> (т.е. пересекает все ребра с пропускной способностью <tex>1</tex>). Поток по каждому пути в декомпозиции не превышает 1, а значит, этих путей не меньше, чем ребер между <tex>A</tex> и <tex>B</tex>, а их <tex>\Omega (E)</tex>.
* По построению сети, любой путь из <tex>s</tex> в <tex>t</tex> содержит хотя бы <tex>\left(\dfrac{V}{3} + 3\right)</tex> ребер, что является <tex>\Omega (V)</tex>.
}}
'''Следствие:''' Алгоритмы, которые могут выписать декомпозицию потока вместе с поиском самого потока ([[Схема алгоритма Диница| Алгоритм Диница]], [[Алгоритм Эдмондса-Карпа]], [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину| Алгоритм Форда-Фалкерсона]] и подобные) не могут работать быстрее чем за <tex>O(VE)</tex>, так как декомпозиция может быть сама по себе большой.
==См. также==
*[[Схема алгоритма Диница| Алгоритм Диница]]
*[[Алгоритм поиска блокирующего потока в ациклической сети]]
==Источники информации==
* [https://youtu.be/PMqO0UCezqo?t=1h39m57s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 11]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]
