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

Определение:

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

Рис. 1. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.

Рис. 2. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.

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

Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. 2). В примере поток является блокирующим и имеет величину 1, в то время как максимальный можно делать сколь угодно большим, увеличивая количество вершин по той же схеме.

См. также

• Алгоритм поиска блокирующего потока в ациклической сети
• Схема алгоритма Диница

Источники

• Алгоритм Диница. Необходимые определения.
• Оригинальная публикация алгоритма трёх индийцев.