Изменения
Новая страница: «Алгоритм масштабирования потока - алгоритм поиска максимального потока путем регулирова…»
Алгоритм масштабирования потока - алгоритм поиска максимального потока путем регулирования пропускной способности ребер.
== Суть ==
Этот алгоритм работает в предположении, что все пропускные способности целые. Пусть <tex>U</tex> - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи (для каждого ребра отведем <tex>n+1:=\lfloor\log U\rfloor+1</tex>). Занумеруем биты с младшего (0-ой) по старший (n-ный). Тогда
<tex>c(u,v)=a_n(u,v)2^n+...+a_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>c_1(u,v):=a_n(u,v)2+a_{n-1}(u,v)-f_0(u,v)2</tex>. Далее наше приближение становится точнее и точнее, пока не станет решением для исходной задачи.
== Оценка сложности ==
Сложность этого алгоритма <tex>O(E^2\log U)</tex>, где <tex>\log U</tex> - количество итераций. Докажем, что сложность каждой итерации <tex>O(E^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>(с_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>.
== Суть ==
Этот алгоритм работает в предположении, что все пропускные способности целые. Пусть <tex>U</tex> - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи (для каждого ребра отведем <tex>n+1:=\lfloor\log U\rfloor+1</tex>). Занумеруем биты с младшего (0-ой) по старший (n-ный). Тогда
<tex>c(u,v)=a_n(u,v)2^n+...+a_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>c_1(u,v):=a_n(u,v)2+a_{n-1}(u,v)-f_0(u,v)2</tex>. Далее наше приближение становится точнее и точнее, пока не станет решением для исходной задачи.
== Оценка сложности ==
Сложность этого алгоритма <tex>O(E^2\log U)</tex>, где <tex>\log U</tex> - количество итераций. Докажем, что сложность каждой итерации <tex>O(E^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>(с_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>.
