Изменения

==ОпределенияОбозначения=={{Определение|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 \leqslant \fracdfrac{P}{F} + 1</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>c_{f_1}(uv) = c(uv) - f_i</tex>, а <tex>c_{f_1}(wv) = c(wv) + f_i</tex>, сложив эти два значения, получим, что <tex>c^+(v)</tex> остается неизменной. Применив такое же рассуждение для <tex>c^-(v)</tex>, получим, что потенциал каждой вершины остается неизменным.

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

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

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

Таким образом <tex>F</tex> ограничен наименьшим из <tex>|V_k||V_{k+1}|</tex>. Но эта величина максимальна, когда <tex>|V_i| = \dfrac{|V|/}{(l+1)}</tex> для <tex>0 \leqslant i \leqslant n</tex>, таким образом <tex>F \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 \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>G_f</tex> {{---}} сеть с максимальным потоком <tex>F - |f| \ge geqslant C^{\frac{1/}{3}}|V|^{\frac{2/}{3}}</tex>. Мы можем применить Лемму(3), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:

<tex>l \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^{\frac{1/}{3}}|V|^{\frac{2/}{3}})</tex> фаз, и <tex>O(C^{\frac{1/}{3}}|V|^{\frac{2/}{3}})</tex> фаз осталось. Теорема доказана.

== Литература См. также ==*[[Схема алгоритма Диница]] == Источники информации ==