Блокирующий поток — различия между версиями
(Метки: правка с мобильного устройства, правка из мобильной версии) |
|||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | <b>Блокирующий поток</b> (англ. ''blocking flow'') {{---}} такой [[Определение сети, потока|поток]]<tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток. | + | <b>Блокирующий поток</b> (англ. ''blocking flow'') {{---}} такой [[Определение сети, потока|поток]] <tex>f</tex> в данной сети <tex>G</tex>, что любой <tex>s \leadsto t</tex> путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток. |
}} | }} | ||
| − | Блокирующий поток не обязательно максимален (пример: см. рис. 1). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети. | + | Блокирующий поток не обязательно максимален (пример: см. рис. <tex>1</tex>). [[Теорема Форда-Фалкерсона]] говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся <tex>s \leadsto t</tex> пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети. |
| − | Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. 2). В примере поток является блокирующим и имеет величину 1, в то время как максимальный можно делать сколь угодно большим, увеличивая количество вершин по той же схеме. | + | Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. <tex>2</tex>). В примере поток является блокирующим и имеет величину <tex>1</tex>, в то время как максимальный можно делать сколь угодно большим, увеличивая количество вершин по той же схеме. |
| − | Блокирующий поток используется в алгоритме Диница. Его поиск с помощью удаляющего обхода занимает <tex>O(VE)</tex> времени. | + | Блокирующий поток используется в [[Схема алгоритма Диница|алгоритме Диница]]. Его поиск с помощью удаляющего обхода занимает <tex>O(VE)</tex> времени. |
{|align="center" | {|align="center" | ||
|-valign="top" | |-valign="top" | ||
| − | |[[Файл:Блокпоток.png|240px|thumb|right|Рис. 1. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]] | + | |[[Файл:Блокпоток.png|240px|thumb|right|Рис. <tex>1</tex>. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]] |
| − | |[[Файл:Блокирующийпоток.png|240px|thumb|right|Рис. 2. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]] | + | |[[Файл:Блокирующийпоток.png|240px|thumb|right|Рис. <tex>2</tex>. Пропускные способности всех рёбер равны единице, по красным рёбрам течёт единичный поток.]] |
|} | |} | ||
Версия 00:21, 19 марта 2018
| Определение: |
| Блокирующий поток (англ. blocking flow) — такой поток в данной сети , что любой путь содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток. |
Блокирующий поток не обязательно максимален (пример: см. рис. ). Теорема Форда-Фалкерсона говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.
Более того, величина блокирующего потока может быть сколь угодно мала по сравнению с величиной максимального потока в сети (пример: см. рис. ). В примере поток является блокирующим и имеет величину , в то время как максимальный можно делать сколь угодно большим, увеличивая количество вершин по той же схеме.
Блокирующий поток используется в алгоритме Диница. Его поиск с помощью удаляющего обхода занимает времени.
