Блокирующий поток — различия между версиями
Proshev (обсуждение | вклад) |
(→Источники) |
||
| Строка 12: | Строка 12: | ||
== Источники == | == Источники == | ||
| − | [http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.] | + | * [http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.] |
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Задача о максимальном потоке ]] | [[Категория: Задача о максимальном потоке ]] | ||
Версия 08:18, 3 февраля 2012
| Определение: |
| Блокирующий поток - такой поток в данной сети , что любой путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток. |
Блокирующий поток не обязательно максимален (пример: см. рис. 1). Теорема Форда-Фалкерсона говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
