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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлена ссылка на оригнальную публикацию алгоритма трёх нидийцев)
(правка не к той статье)
Строка 16: Строка 16:
 
== Источники ==
 
== Источники ==
 
* [http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]
 
* [http://www.e-maxx.ru/algo/dinic Алгоритм Диница. Необходимые определения.]
*[http://eprints.utas.edu.au/160/1/iplFlow.pdf Оригинальная публикация алгоритма трёх индийцев.]
+
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о максимальном потоке ]]
 
[[Категория: Задача о максимальном потоке ]]

Версия 20:02, 21 ноября 2013

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


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

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

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

См. также

Источники