50
правок
Изменения
м
→Теоремы: Опечатка в доказательстве
|statement=Число итераций [[Схема алгоритма Диница|алгоритма Диница]] в сети <tex>N</tex> (<tex>s</tex> — исток, <tex>t</tex> — сток) с целочисленными пропускными способностями — <tex>O(\sqrt{P})</tex>.
|proof=
Пусть <tex>F</tex> - максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на 1. Если <tex>F > \sqrt{P}</tex>, рассмотрим последнюю фазу, на момент начала выполнения которой поток в сети был меньше, чем <tex>F - \sqrt{P}</tex>. После этого потребуется не больше <tex>\sqrt{P}</tex> фаз, чтобы найти максимальный поток. На предыдущей фазе поток (<tex>f</tex>) в <tex>N</tex> был не больше <tex>F-\sqrt{P}</tex>, таким образом <tex>F-|f| \leq geqslant \sqrt{P}</tex>.
<tex>N(f)</tex> - сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex>, и получить оценку длины <tex>l</tex> слоистой сети:
