251
правка
Изменения
м
Нет описания правки
Количество необходимых увеличений путей, основанных на кратчайших путях, может быть много больше количества увеличений, основанных на путях с высокой пропускной способностью.
{|border="0" cellpadding="5" width=30% align=center
|[[Файл:Flow_scale_1.png|550px330px|thumb|center|Выбор дополняющих путей в порядке длины]]|[[Файл:Flow_scale_2.png|550px330px|thumb|center|Выбор пути с высокой пропускной способностью в первую очередь]]
|}
Максимальный поток в сети <tex> G </tex> ограничен сверху значением <tex> |f_k| + 2^k E </tex>, где <tex> |f_k| </tex> {{---}} значение потока при масштабе <tex> \Delta = 2^k </tex>.
|proof=
[[Файл:Flow_scale_3.png|580px350px|thumb|right|Разрез <tex> C_k </tex>]]
В конце итерации с масштабом <tex> \Delta = 2^k </tex>, сеть <tex> G_{f_k} </tex> может быть разбита на два непересекающихся множества <tex> A_k </tex> и <tex> \overline{A_k} </tex> так, что остаточная пропускная способность каждого ребра, идущего из <tex> A_k </tex> в <tex> \overline{A_k} </tex>, не превосходит масштаба <tex> \Delta </tex>. То есть образуется [[Разрез,_лемма_о_потоке_через_разрез|разрез]] <tex> C_k = \langle A_k, \overline{A_k} \rangle </tex>.
== Псевдокод ==
'''function''' maxFlowByScalingMax_Flow_By_Scaling(G: '''graph''', s: '''int''', t: '''int'''): '''int''' '''int''' flow = 0 <font color=darkgreentex> // поток в сети f \leftarrow 0 </fonttex> '''int''' scale = <tex>\Delta \leftarrow 2^{\lfloor\log_2U\rfloor}</tex> <font color=darkgreen> // текущий минимальный размер потока, который пытаемся пустить </font> '''while''' scale <tex> \geqslant Delta \geq 1 </tex> 1 '''do while''' в <tex> G_f </tex> существует увеличивающий путь <tex> p </tex> с пропускной способностью не меньше, чем scaleменьшей <tex> \Delta </tex> '''intdo''' minCapacity = <tex>\delta \leftarrow \min\{c(u, v) \colon(u, v) \in p\} </tex> <font color=darkgreen> // минимальная пропускная способность в увеличивающем пути </font> увеличить поток по рёбрам <tex> p </tex> на minCapacity<tex> \delta </tex> обновить <tex> G_f </tex> flow = flow <tex> f \leftarrow f + minCapacity\delta </tex> scale = scale <tex> \Delta \leftarrow \Delta / 2</tex> '''return''' flow<tex> f </tex>
== См. также ==
* [[Определение_сети,_потока|Определение сети, потока]]
* [http://www.csd.uwo.ca/~yuri/Papers/iccv07_cap_scaling.pdf ''Olivier Juan, Yuri Boikov'': Capacity Scaling for Graph Cuts in Vision]
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited Algorithm Tutorials. Maximum Flow: Augmenting Path Algorithms Comparison]
* [http://logic.pdmi.ras.ru/ics/talks/21stream.pdf ''Андрей Станкевич'': Задача о максимальном потоке]
* [https://youtu.be/sEwp5ZAJJps?t=18m9s ''Андрей Станкевич'': Лекториум, дополнительные главы алгоритмов, лекция 12]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
