Изменения
Нет описания правки
== Суть ==
Этот алгоритм работает в предположении, что все пропускные способности ребер целые. Пусть есть граф <tex>G</tex>, <tex>\forall (u,v)\in E\colon u_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сначала путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток. Пусть <tex>U</tex> - максимальная пропускная способность. Введем параметр <tex>\Delta</tex>. Это большое число, к примеру, равное <tex>U</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше <tex>\Delta</tex> и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым <tex>\Delta</tex>. При <tex>\Delta == 1</tex> алгоритм масштабирования идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса - Карпа]], поэтому алгоритм масштабирования корректен.
== Оценка сложности ==
На каждом шаге алгоритм выполняет <tex>O(E)</tex> увеличений потока в худшем случае. Докажем это. <tex>\Delta = 2^k</tex>. В конце шага множество вершин множество вершин можно разбить на две части: <tex>A_k</tex> и <tex>\overline{A_k}</tex>. Все ребра выходящие из <tex>A_k</tex> имеют остаточную пропускную способность менее <tex>2^k</tex>. Наибольшее количество ребер между <tex>A_k</tex> и <tex>\overline{A_k} равно E. Итого остаточный поток(поток, который может быть получен на оставшихся шагах) на текущей фазе с <tex>k</tex> максимально составляет <tex>2^kE</tex>. Каждый увеличивающий путь при данном <tex>k</tex> имеет пропускную способность как минимум <tex>2^k</tex>. На предыдущем шаге с масштабом <tex>k+1</tex> остаточный поток, который может быть получен на последующих фазах, ограничен <tex>2^{k+1}E</tex>. Значит максимальное число появившихся увеличивающих путей равно <tex>2E</tex>. Увеличивающий путь можно найти за <tex>O(E)</tex>, используя [[Обход_в_ширину | BFS]]. Количество шагов <tex>O(log_2U)</tex>. Итоговая сложность <tex>O(E^2log_2U)</tex>.
== Псевдокод ==
<tex>\Delta\leftarrow\Delta/2</tex>
'''return''' f
== Литература ==
* [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]
