1632
правки
Изменения
м
rollbackEdits.php mass rollback
Положим, что <tex>F > C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>, и рассмотрим последнюю фазу, в которой поток <tex>f</tex> не превышает <tex>F - C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>. В этот момент осталось не более <tex>C^{\frac{1}{3}}|V|^{\frac{2}{3}} + 1</tex> фаз, и <tex>G_f</tex> {{---}} сеть с максимальным потоком <tex>F - |f| \geqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>. Мы можем применить Лемму(3), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:
<tex>l \leqslant |V|{\left(\dfrac{2C}{F-|f|}\right)}^{\frac{1}{2}} - 1 \leqslant 2^{\frac{1}{2}}C^{\frac{1}{3}}|V|^{\frac{2}{3}} - 1</tex>.
Таким образом, прошло <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex> фаз, и <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex> фаз осталось.
