Изменения

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

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

Нет изменений в размере, 15:38, 7 января 2017
Нет описания правки
[[Файл:Блокпоток.png|240px|thumb|right|Рис. 1. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
[[Файл:Блокирующийпоток.png|240px|thumb|right|Рис. 2. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
{{Определение
|definition=
<b>Блокирующий поток</b> (англ. ''blocking flow'') {{---}} такой поток <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
}}
[[Файл:Блокпоток.png|240px|thumb|right|Рис. 1. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
[[Файл:Блокирующийпоток.png|240px|thumb|right|Рис. 2. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
Блокирующий поток не обязательно максимален (пример: см. рис. 1). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
Анонимный участник

Навигация