Изменения

Перейти к: навигация, поиск

Блокирующий поток

55 байт добавлено, 00:21, 19 марта 2018
Нет описания правки
}}
Блокирующий поток не обязательно максимален (пример: см. рис. <tex>1</tex>). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. <tex>2</tex>). В примере поток является блокирующим и имеет величину <tex>1</tex>, в то время как максимальный можно делать сколь угодно большим, увеличивая количество вершин по той же схеме.
Блокирующий поток используется в [[Схема алгоритма Диница|алгоритме Диница]]. Его поиск с помощью удаляющего обхода занимает <tex>O(VE)</tex> времени.
{|align="center"
|-valign="top"
|[[Файл:Блокпоток.png|240px|thumb|right|Рис. <tex>1</tex>. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]] |[[Файл:Блокирующийпоток.png|240px|thumb|right|Рис. <tex>2</tex>. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
|}
693
правки

Навигация