Изменения
Нет описания правки
Этот алгоритм работает в предположении, что все пропускные способности целые. Пусть <tex>U</tex> - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи (для каждого ребра отведем <tex>n+1:=\lfloor\log U\rfloor+1</tex>). Занумеруем биты с младшего (0-ой) по старший (n-ный). Тогда
<tex>\forall (u,v)\in E:c(u,v)=a_n2^na_n(u,v)2^n+...+a_12a_1(u,v)2+a_0(u,v); a_i(u,v)\in\{0,1\}</tex>
Будем решать задачу методом Форда-Фалкерсона сначала для графа с урезанными пропускными способностями <tex>c_0(u,v):=a_n(u,v)</tex>. Решив ее и получив поток <tex>f_0</tex>, добавим следующий бит и вычтем грубое приближение. То есть <tex>\forall (u,v)\in E:c_1(u,v):=a_n2a_n(u,v)2+a_{n-1}(u,v)-f_02f_0(u,v)2</tex>. Далее наше приближение становится точнее и точнее, пока не станет решением для исходной задачи.
== Оценка сложности ==
На первой итерации мы имеем только ребра веса 1. Это значит, что <tex>|f|\le V</tex>. Значит количество итераций (дополняющих путей) не превосходит <tex>V</tex>, поиск доп. пути занимает <tex>O(E)</tex>. Получаем сложность <tex>O(VE)\le O(E^2)</tex>.
Теперь рассмотрим переход ко второй итерации. Граф <tex>G_{f_0}</tex> несвязен. Рассмотрим разрез <tex>(S,T)</tex>, где <tex>S</tex> и <tex>T</tex> - компоненты связности. <tex>(с_0c_0)_{f_0}(S,T)=0</tex>. Значит в новом графе с пропускными способностями <tex>c_1</tex>: <tex>\forall u\in S, v\in T:c_1(u,v)\le1</tex>. Так как <tex>(S,T)</tex> - разрез, то <tex>|f'_1|=f'_1(S,T)\le c(S,T)\le E</tex>. Здесь <tex>f'_1</tex> - максимальный поток в <tex>G_1</tex> с пропускными способностями <tex>c_1</tex>, а <tex>f_1=f_0+f'_1</tex>. Так как пропускная способность каждого дополняющего пути не меньше 1, мы получили оценку на количество итераций. Дополняющий путь же мы можем найти за <tex>O(E)</tex>.
