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

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

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

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

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

Блокирующий поток используется в алгоритме Диница. Его поиск с помощью удаляющего обхода занимает [math]O(VE)[/math] времени.

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

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

См. также

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

Источники

• Алгоритм Диница. Необходимые определения.
• Wikipedia — Dinic's algorithm
• Википедия — алгоритм Диница