272
правки
Изменения
→Оценка сложности
Время работы алгоритма — <tex> O(E^2 \log U) </tex>.
|proof=
Количество итераций — <tex> O(\log U) </tex>. Докажем, что сложность каждой итерации — <tex> O(E^2) </tex>.
На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq |VG| </tex>. Поиск каждого дополнительного пути требует <tex> O(E) </tex> времени, а их количество не больше <tex> V </tex>. Итоговая сложность первой итерации — <tex> O(VE) \leq O(E^2) </tex>.
[[Файл:Scaling.jpg|250px|thumb|right|Разрез <tex> (A, \overline{A}) </tex>.]]
Докажем оценку для второго шага (для остальных доказательство аналогично).
Граф <tex> G_{f_0} </tex> — несвязен. Пусть <tex> A </tex> — компонента связности, <tex> s \in A, t \in \overline{A} </tex>. Тогда <tex> c_{0_{f_0}}(A, \overline{A}) = 0 </tex>. Значит в графе с пропускными способностями <tex> c_1 </tex>:
<tex> \forall u \in A, v \in \overline{A} \colon c_1(u, v) \leq 1 </tex>.
}}
