Изменения

|statement=Пусть <tex>f</tex> - блокирующий поток в графе сети <tex>G</tex>. <tex>s</tex>, <tex>t</tex> - исток и сток, соответственно. Тогда <tex>\rho_{G}(s, t) < \rho_{G_{f}}(s, t)</tex>.

Для v - вершины, не являющаейся являющейся истоком или стоком:

|statement=Чило Число итераций алгоритма Диница в сети <tex>G </tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями - <tex>O(\sqrt{c(G)})</tex>.|proof=доказательство Разобьём все итерации на 2 группы: 1). Короткие фазы - когда <tex>\rho(s, t) \leq k</tex>. 2). Длинные фазы - когда <tex>\rho(s, t) > k</tex>. Коротких фаз - <tex>O(k)</tex> штук, т.к. после каждой итерации <tex>\rho(s, t)</tex> увеличивается, но не может быть больше <tex>k</tex>. Длинные фазы:Число длинных фаз <tex>\leq</tex> количество путей из <tex>s</tex> в <tex>t</tex> длины "<tex> > k</tex>" <tex> \leq \frac{\sum\limits_{v \in V} c(v)}{k} = \frac{c(G)}{k}</tex>. (т.к. через вершину <tex>v</tex> не может пройти больше <tex>c(необязательноv)</tex> путей, а на каждом пути лежит <tex>\geq k</tex> вершин.) Получается, что число длинных фаз - <tex>O(\frac{c(G)}{k})</tex>. Давайте возьмём <tex>k = \sqrt{c(G)}</tex>. Получим, что количество фаз - <tex>O(\sqrt{c(G)})</tex>. А, значит, что количество итераций тоже - <tex>O(\sqrt{c(G)})</tex>.}} {{Теорема|id=th2|about=Вторая теорема Карзанова|statement=Число итераций алгоритма Диница в сети <tex>G</tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями меньше <tex>c_{max}</tex> - <tex>O(\sqrt[3]{{|V|}^2 c_{max}})</tex>.