Изменения
→Теоремы
|id=th1.
|about=Первая теорема Карзанова
|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 \sqrt{P}</tex>.
