Изменения

==ОпределенияОбозначения=={{Определение|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-t</tex> пути в <tex>G_f</tex>[[Дополняющая сеть, дополняющий путь|остаточная сеть]].}}

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

Но суммарное количество потока, которое может проходить через любую вершину не превосходит ее её потенциала.

Пусть По [[Теорема_о_декомпозиции | теореме о декомпозиции]] поток можно разбить на множество простых путей из <tex>c_fs</tex> {{---}} функция пропускных способностей в <tex>G_ft</tex>и циклов. Рассмотрим каждый путь (цикл) и убедимся, а что, пуская по нему поток <tex>p_f(v), in_f(v), out_f(v)f_i</tex> {{---}} , потенциалвершины не изменится. Действительно, множество входящих ребер и множество выходящих ребер вершины рассмотрим вершину <tex>v</tex> из <tex>G_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_fc^-(v)} c_f(e) = \sum_{e\in out(v)}c(e)</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>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 \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 \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|{\left(\fracdfrac{2C}{F-|f|}\right)}^{\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> фаз осталось. Теорема доказана.

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