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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
 
[[Файл:Блокпоток.png|240px|thumb|right|Рис. 1. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
 
[[Файл:Блокпоток.png|240px|thumb|right|Рис. 1. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
 +
[[Файл:Блокирующийпоток.png|240px|thumb|right|Рис. 2. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]]
 
Блокирующий поток не обязательно максимален (пример: см. рис. 1). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
 
Блокирующий поток не обязательно максимален (пример: см. рис. 1). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
  
Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. 2).
+
Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. 2). В примере поток является блокирующим и имеет величину 1, в то время как максимальный можно делать сколь угодно большим, увеличивая количество вершин по той же схеме.
  
 
== См. также ==
 
== См. также ==

Версия 01:12, 25 декабря 2012

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


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

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

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

См. также

Источники