Изменения

==ОпределенияОбозначения=={{Определение|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(c^{+}(v), c^{-}(v))</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 P_i</tex>, таким образом получаем:

для любого допустимого потока <tex>f</tex>. В частности, <tex>(l - 1)F \leq \displaystyle \sum_{i = 1}^{l - 1} leqslant P_i \leq P</tex>, таким образом получаем:

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

Пусть По [[Теорема_о_декомпозиции | теореме о декомпозиции]] поток можно разбить на множество простых путей из <tex>c_fs</tex> - функция пропускных способностей в <tex>N(f)t</tex>и циклов. Рассмотрим каждый путь (цикл) и убедимся, а что, пуская по нему поток <tex>p_f(v), in_f(v), out_f(v)f_i</tex> - , потенциалвершины не изменится. Действительно, множество входящих ребер и множество выходящих ребер вершины рассмотрим вершину <tex>v</tex> из <tex>N(f)</tex>.  Достаточно доказать, что поток <tex>p_f(v) = p(v)f_i</tex>. Ребру в неё течёт по ребру <tex>euv</tex> , а из неё по ребру <tex>in(v)vw</tex> соответствуют ребро . Пусть <tex>e_1c_{f_i}</tex> из {{---}} функция пропускных способностей в остаточной сети после пропускания потока по <tex>in_f(v)i</tex> с пропускной способностью <tex>c(e) - fому пути (eциклу)</tex>, и ребро . Рассмотрим <tex>e_2</tex> из <tex>outc^+_{f_1}(v)</tex> с пропускной способностью <tex>f= c_{f_1}(euv)</tex>. Аналогично, ребру <tex>e</tex> из <tex>out+ c_{f_1}(vwv)</tex> соответствуют ребра из . <tex>out_fc_{f_1}(vuv)</tex> с пропускной способностью <tex>= c(vuv) - f (v)f_i</tex> и , а <tex>in_fc_{f_1}(vwv)</tex> с пропускной способностью <tex>f= c(ewv)+ f_i</tex>. Используя правило сохранения потока, нетрудно проверитьсложив эти два значения, получим, что <tex>\displaystyle\sum_{e\in in_f(v)} c_f(e) = \sum_{e\in inc^+(v)}c(e)</tex> и остаётся неизменной. Применив такое же рассуждение для <tex>\displaystyle\sum_{e\in out_f(v)} c_f(e) = \sum_{e\in outc^-(v)}c(e)</tex> , получим, что и требовалось доказатьпотенциал каждой вершины остаётся неизменным.

|statement=Число итераций [[Схема алгоритма Диница |алгоритма Диница]] в сети <tex>N</tex> (<tex>s</tex>— исток, <tex>t</tex> - исток и — сток, соответственно.) с целочисленными пропускными способностями - — <tex>O(\sqrt{P})</tex>.

Пусть <tex>F</tex> {{-- -}} максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq leqslant \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на <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| \leq 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 \fracdfrac{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{\fracdfrac{2C}{F}} - 1</tex>.

Как и раньше, обозначим Обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множество Множества <tex>X = \bigcup_bigcup\limits_{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| = \dfrac{|V|/}{(l+1)}</tex> для <tex>0 \leq leqslant i \leq leqslant n</tex>, таким образом <tex>F \leq leqslant 2C\dfrac{|V|^2}{ (l+1)^2}</tex>. Выражая <tex>l</tex> получаем нужное, из чего следует необходимое неравенство.

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

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

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

Таким образом, прошло <tex>O(C^{\leq 2frac{1}{3}}|V|^{1/\frac{2}{3}})</tex> фаз, и <tex>O(C^{\frac{1/}{3}}|V|^{\frac{2/}{3} - 1})</tex>фаз осталось. }} == См. также ==*[[Схема алгоритма Диница]] == Источники информации ==* [http://www.springerlink.com/content/w0q006u3631gg124/fulltext.pdf On the efficiency of Maximum-Flow Algorithms on Networks with Small Integer Capacities. David Fernandez-Baca and Charles U.Martel]* [https://www.youtube.com/watch?v=sEwp5ZAJJps&feature=youtu.be&t=26m41s Андрей Станкевич: Лекториум, дополнительные главы алгоритмов, лекция 12]