Алгоритм масштабирования потока

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

Суть

Этот алгоритм работает в предположении, что все пропускные способности ребер целые. Пусть у нас есть граф [math]G[/math], [math]\forall (u,v)\in E: u_{(u,v)}\in\mathbb N[/math]. Пусть [math]U[/math] - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи, выделив для каждого ребра [math]n:=\lfloor\log U\rfloor+1[/math] памяти. Занумеруем биты с младшего (0-ой) по старший (n-ный). Тогда

[math]\forall (u,v)\in E:c(u,v)=2^n*a_n(u,v)+...+2*a_1(u,v)+a_0(u,v); a_i(u,v)\in\{0,1\}[/math]

Будем решать задачу методом Форда-Фалкерсона сначала для графа с урезанными пропускными способностями [math]c_0(u,v):=a_n(u,v)[/math]. Решив ее и получив поток [math]f_0[/math], добавим следующий бит и вычтем грубое приближение. То есть [math]\forall (u,v)\in E:c_1(u,v):=2*a_n(u,v)+a_{n-1}(u,v)-2*f_0(u,v)[/math]. Далее наше приближение становится точнее и точнее, пока не станет решением для исходной задачи.

Оценка сложности

Сложность этого алгоритма [math]O(E^2\log U)[/math], где [math]\log U[/math] - количество итераций. Докажем, что сложность каждой итерации [math]O(E^2)[/math].

На первой итерации мы имеем только ребра веса 1. Это значит, что [math]|f|\le V[/math]. Значит количество итераций (дополняющих путей) не превосходит [math]V[/math], поиск доп. пути занимает [math]O(E)[/math]. Получаем сложность [math]O(VE)\le O(E^2)[/math].

Теперь рассмотрим переход ко второй итерации. Граф [math]G_{f_0}[/math] несвязен. Рассмотрим разрез [math](S,T)[/math], где [math]S[/math] и [math]T[/math] - компоненты связности. [math](c_0)_{f_0}(S,T)=0[/math]. Значит в новом графе с пропускными способностями [math]c_1[/math]: [math]\forall u\in S, v\in T:c_1(u,v)\le1[/math]. Так как [math](S,T)[/math] - разрез, то [math]|f'_1|=f'_1(S,T)\le c(S,T)\le E[/math]. Здесь [math]f'_1[/math] - максимальный поток в [math]G_1[/math] с пропускными способностями [math]c_1[/math], а [math]f_1=f_0+f'_1[/math]. Так как пропускная способность каждого дополняющего пути не меньше 1, мы получили оценку на количество итераций. Дополняющий путь же мы можем найти за [math]O(E)[/math].