Изменения

Пусть <tex>N = (V,E,s,t,c)</tex> {{- --}} [[Определение сети, потока|сеть]] с целочисленными пропускными способностями.

Обозначим <tex>C= \max\limits_{uv \in E} c_{uv}</tex> и <tex>F</tex>, как максимальная пропускная способность ребра и максимальный поток соответственно.

<tex>p(v) = min\big\{c^{+}(v), c^{-}(v)\big\}</tex> {{- --}} потенциал вершины <tex>v</tex>.

[[Дополняющая сеть, дополняющий путь|Остаточную сеть]] обозначим <tex>N(f)G_f</tex>.Обозначим длину [[Схема алгоритма Диница|слоистой сети]] <tex>l</tex> {{- --}} как длину кратчайшего <tex>s-t</tex> пути в <tex>N(f)G_f</tex>.

Пусть <tex>l</tex> {{- --}} расстояние между <tex>s</tex> и <tex>t</tex> в исходной сети с текущим потоком, равным 0, и максимальным потоком, равным максимальный поток в этой сети равен <tex>F</tex>.

Тогда <tex>l \leq leqslant \frac{P}{F} + 1</tex>

Пусть <tex>l</tex> {{- --}} расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex> {{--- }} набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(i \leq leqslant l)</tex>. <tex>V_i</tex> {{--- }} разъединяющее множество узлов: при его удалении исчезают все пути из <tex>s</tex> в <tex>t</tex>.

<tex>|f| \leq leqslant P_i</tex>

для любого допустимого потока <tex>f</tex>. В частности, <tex>F \leq leqslant P_i</tex>, таким образом получаем:

<tex>(l - 1)F \leq leqslant \displaystyle \sum_{i = 1}^{l - 1} P_i \leq leqslant P</tex>

Пусть <tex> N </tex> {{- --}} сеть, а <tex>f</tex> {{- --}} допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>N(f)G_f</tex> равен общему потенциалу <tex>N</tex>.

Пусть <tex>c_f</tex> {{- --}} функция пропускных способностей в <tex>N(f)G_f</tex>, а <tex>p_f(v), in_f(v), out_f(v)</tex> {{--- }} потенциал, множество входящих ребер и множество выходящих ребер вершины <tex>v</tex> из <tex>N(f)G_f</tex>.

Пусть <tex>F</tex> {{- --}} максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq leqslant \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| \geqslant \sqrt{P}</tex>.

<tex>N(f)G_f</tex> {{--- }} сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>N(f)G_f</tex>, и получить оценку длины <tex>l</tex> слоистой сети:

<tex>l \leq leqslant \frac{P}{F-|f|} + 1</tex>

Пусть в сети <tex>N</tex> нет [[Основные определения теории графов#def1|параллельных ребер]]. Пусть <tex>fF</tex> {{-- поток в <tex>N</tex>, а <tex>F</tex> - }} максимальный поток в <tex>N(f)</tex>. Тогда расстояние <tex>l</tex> между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex> таково: <tex>l \leq leqslant |V|\sqrt{\frac{2C}{F}} - 1</tex>.

Обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множества <tex>X = \bigcup_{i = 0}^k V_i</tex> и <tex>Y = V - X</tex> определяют разрез <tex>(X, Y)</tex>. Пропускная способность этого разреза не больше <tex>2C|V_k||V_{k + 1}|</tex>, так как все ребра между <tex>X</tex> и <tex>Y</tex> также являются ребрами между <tex>V_k</tex> и <tex>V_{k+1}</tex> и не более чем двумя параллельными ребрами, исходящими из какой-то вершины в остаточной сети. По теореме о максимальном потоке/минимальном разрезе, <tex>F \leq leqslant 2C|V_k||V_{k+1}|</tex>.Таким образом <tex>F</tex> ограничен наименьшим из <tex>|V_k||V_{k+1}|</tex>. Но эта величина максимальна, когда <tex>|V_i| = |V|/(l+1)</tex> для <tex>0 \leq leqslant i \leq leqslant n</tex>, таким образом <tex>F \leq leqslant 2C|V|^2 / (l+1)^2</tex>. Выражая <tex>l</tex>, получаем нужное.

|statement=Число итераций алгоритма Диница с целочисленными пропускными способностями {{- --}} <tex>O(C^{1/3}|V|^{2/3})</tex>.

Если <tex>F \leq leqslant C^{1/3}|V|^{2/3}</tex>, то теорема очевидна. Положим, что <tex>F > C^{1/3}|V|^{2/3}</tex>, и рассотрим последнюю фазу, в которой поток <tex>f</tex> не превышает <tex>F - C^{1/3}|V|^{2/3}</tex>. В этот момент осталось не более <tex>C^{1/3}|V|^{2/3} + 1</tex> фаз, и <tex>N(f)G_f</tex> {{--- }} сеть с максимальным потоком <tex>F - |f| \ge C^{1/3}|V|^{2/3}</tex>. Мы можем применить Лемму(23), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:

<tex>l \leq leqslant |V|{(\frac{2C}{F-|f|})}^{1/2} - 1 </tex> <tex>\leq leqslant 2^{1/2}C^{1/3}|V|^{2/3} - 1</tex>.