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

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

Версия 00:14, 25 декабря 2012

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


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

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

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

См. также

Источники