Изменения

{{Определение==Обозначения==|definition=Введём следующие обозначения:Пусть * <tex>N = (V,E,s,t,c)</tex> {{- --}} [[Определение сети, потока|сеть ]] с целочисленными пропускными способностями.,Обозначим * обозначим <tex>C= \max\limits_{uv \in E} c_{uv}</tex> и <tex>F</tex>, как максимальная пропускная способность ребра и максимальный поток соответсвенно.,*<tex>c^{+}(v) = \sum\limits_{uv \in E} c_{uv}</tex>.,*<tex>c^{-}(v) = \sum\limits_{vu \in E} c_{vu}</tex>.,*<tex>p(v) = \min\big\{(c^{+}(v), c^{-}(v)\big\})</tex> {{-- -}} потенциал вершины <tex>v</tex>. Тогда общий потенциал выражается формулой:,*<tex>P = \sum\limits_{v \in V, v \neq s,t}p(v)</tex>.{{---}} общий потенциал,*<tex>G_f</tex> {{---}}[[Дополняющая сеть, дополняющий путь|остаточная сеть]].

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

Тогда <tex>l \leq leqslant \fracdfrac{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</tex> обозначить как любой допустимый поток, то <tex>|f|</tex> единиц потока должно проходить через <tex>V_i</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>s</tex> в <tex>t</tex> и циклов. Рассмотрим каждый путь (цикл) и убедимся, что, пуская по нему поток <tex>f_i</tex>, потенциал вершины не изменится. Действительно, рассмотрим вершину <tex>v</tex>, поток <tex>f_i</tex> в неё течёт по ребру <tex>uv</tex>, а из неё по ребру <tex>vw</tex>. Пусть <tex>с_аc_{f_i}</tex> {{- --}} функция пропускных способностей в остаточной сети после пропускания потока по <tex>i</tex>-ому пути (циклу). Рассмотрим <tex>c^+_{f_1}(v) = c_{f_1}(uv) + c_{f_1}(wv)</tex>. <tex>Nc_{f_1}(uv) = c(fuv)- f_i</tex>, а <tex>p_fc_{f_1}(wv) = c(vwv)+ f_i</tex>, сложив эти два значения, получим, in_fчто <tex>c^+(v), out_f</tex> остаётся неизменной. Применив такое же рассуждение для <tex>c^-(v)</tex>, получим, что потенциал каждой вершины остаётся неизменным.

|statement=Число итераций [[Схема алгоритма Диница |алгоритма Диница]] в сети <tex>GN</tex> (<tex>s</tex>— исток, <tex>t</tex> - исток и — сток, соответственно.) с целочисленными пропускными способностями - — <tex>O(\sqrt{c(G)P})</tex>.|proof=Разобьём все итерации Пусть <tex>F</tex> {{---}} максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leqslant \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на 2 группы:<tex>1</tex>. Если <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>G_f</tex> {{---}} сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1). Короткие фазы - когда , чтобы оценить расстояние между <tex>\rho(s</tex> и <tex>t</tex> в <tex>G_f</tex>, t) \leq kи получить оценку длины <tex>l</tex>.слоистой сети:

2). Длинные фазы - когда <tex>l \leqslant \rho(s, t) > kdfrac{P}{F-|f|} + 1</tex>.

Коротких фаз - <tex>O(k)</tex> штукТак как каждая фаза увеличивает длину слоистой сети минимум на один, т.к. после каждой итерации то осуществляется не больше <tex>\rho(s, t)sqrt{P}</tex> увеличивается, но фаз. Таким образом происходит не может быть больше более <tex>k2\sqrt{P}</tex>фаз.}}

Длинные фазы:{{Лемма|about = 3|statement=Число длинных фаз Пусть в сети <tex>N</tex> нет [[Основные определения теории графов#def1|параллельных рёбер]]. Пусть <tex>F</tex> {{---}} максимальный поток в <tex>N</tex>\leq. Тогда расстояние <tex>l</tex> количество путей из между <tex>s</tex> в и <tex>t</tex> длины больше в <tex>kN</tex> таково: <tex> l \leq leqslant |V|\fracsqrt{\sum\limits_dfrac{v \in V2C} c(v){F}{k} - 1</tex>.|proof=Обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множества <tex>X = \fracbigcup\limits_{ci = 0}^k V_i</tex> и <tex>Y = V - X</tex> определяют разрез <tex>(GX, Y)}</tex>. Пропускная способность этого разреза не больше <tex>2C|V_k||V_{k+ 1}|</tex>, так как все рёбра между <tex>X</tex>. (т.к. через вершину и <tex>vY</tex> не может пройти больше также являются рёбрами между <tex>c(v)V_k</tex> путей, а на каждом пути лежит и <tex>\geq V_{k+1}</tex> вершини не более чем двумя параллельными рёбрами, исходящими из какой-то вершины в остаточной сети.) ПолучаетсяПо теореме о максимальном потоке/минимальном разрезе, что число длинных фаз - <tex>O(F \frac{c(G)}leqslant 2C|V_k||V_{k+1})|</tex>. Давайте возьмём Таким образом <tex>F</tex> ограничен наименьшим из <tex>|V_k||V_{k = \sqrt{c(G)+1}|</tex>. ПолучимНо эта величина максимальна, что количество фаз - когда <tex>O(|V_i| = \sqrtdfrac{|V|}{c(Gl+1)})</tex>. А, значитдля <tex>0 \leqslant i \leqslant n</tex>, что количество итераций тоже - таким образом <tex>O(F \leqslant 2C\sqrtdfrac{|V|^2 }{c(Gl+1)^2})</tex>, из чего следует необходимое неравенство.

|statement=Число итераций алгоритма Диница с целочисленными пропускными способностями {{---}} <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex>.|proof=Если <tex>F \leqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>, то теорема очевидна. Положим, что <tex>F > C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>, и рассмотрим последнюю фазу, в сети которой поток <tex>Gf</tex> (не превышает <tex>F - C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>s. В этот момент осталось не более <tex>C^{\frac{1}{3}}|V|^{\frac{2}{3}} + 1</tex>фаз, и <tex>tG_f</tex> {{--- исток }} сеть с максимальным потоком <tex>F - |f| \geqslant C^{\frac{1}{3}}|V|^{\frac{2}{3}}</tex>. Мы можем применить Лемму(3), чтобы оценить длину <tex>l</tex> слоистой сети, и сток, соответственно, количество выполненных фаз: <tex>l \leqslant |V|{(\dfrac{2C}{F-|f|})}^{\frac{1}{2}} - 1 \leqslant 2^{\frac{1}{2}}C^{\frac{1}{3}}|V|^{\frac{2}{3}} - 1</tex>.) с целочисленными пропускными способностями меньше  Таким образом, прошло <tex>c_O(C^{max\frac{1}{3}}|V|^{\frac{2}{3}})</tex> - фаз, и <tex>O(C^{\sqrt[3]frac{1}{3}}|V|}^{\frac{2 c_}{max3}})</tex>фаз осталось.