Изменения

Алгоритм масштабирования потока - — алгоритм поиска максимального потока путем регулирования пропускной способности ребер.

Пусть есть существует граф <tex>G</tex>, и <tex>\forall (u,v)\in E\colon u_c_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сначала сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать потокпо этим путям, а затем всех остальных. Пусть <tex>U</tex> - максимальная пропускная способность. Введем Введём параметр <tex>\Delta = 2^{\lfloor\log_2U\rfloor}</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}</tex> равно <tex>E</tex>. Итого Следовательно, остаточный поток(поток, который может быть получен на оставшихся шагах) на текущей фазе с текущим значением <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^2\log_2U)</tex>.