Блокирующий поток — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
== Источники ==
 
== Источники ==
 
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]
 
[http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о максимальном потоке ]]

Версия 07:13, 18 января 2012

Определение:
Блокирующий поток - такой поток [math]f[/math] в данной сети [math]G[/math], что любой [math]s \leadsto t[/math] путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток.


Рис. 1

Блокирующий поток не обязательно максимален (пример: см. рис. 1). Теорема Форда-Фалкерсона говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся [math]s \leadsto t[/math] пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

См. также

Источники

Алгоритм Диница. Необходимые определения.