16
правок
Изменения
Новая страница: «{{Определение |definition= <b>Блокирующий поток</b> - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что л…»
{{Определение
|definition=
<b>Блокирующий поток</b> - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
}}
Блокирующий поток не обязательно максимален. [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
== См. также ==
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Схема алгоритма Диница]]
== Источники ==
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]
|definition=
<b>Блокирующий поток</b> - такой поток <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.
}}
Блокирующий поток не обязательно максимален. [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
== См. также ==
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Схема алгоритма Диница]]
== Источники ==
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]
