Изменения

|idabout =lemma1.1|statement=Пусть <tex>fl</tex> {{- блокирующий поток в графе <tex>G</tex>. --}} расстояние между <tex>s</tex>, и <tex>t</tex> - исток и стокв исходной сети, соответственно. Тогда максимальный поток в этой сети равен <tex>\rho_{G}(s, t) < \rho_{G_{f}}(s, t)F</tex>.}}

Тогда <tex>l \leqslant \dfrac{P}{Определение|definition=В графе G, в котом s, t - исток и сток, соответственноF} + 1</tex>.Для v - вершины, не являющаейся истоком или стоком:

|proof=Пусть <tex>l</tex> {{---}} расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex>c^{+{---}}набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(vi \leqslant l) = \sum\limits_</tex>. <tex>V_i</tex> {{uv \in E---} c_{uv}разъединяющее множество узлов: при его удалении исчезают все пути из <tex>s</tex> в <tex>t</tex>.Следуя закону [[Определение сети, потока|сохранения потока]], если <tex>f</tex> обозначить как любой допустимый поток, то <tex>|f|</tex> единиц потока должно проходить через <tex>V_i</tex>.Но суммарное количество потока, которое может проходить через любую вершину не превосходит её потенциала. Отсюда, если обозначить <tex>P_i</tex> как общий потенциал вершин из <tex>V_i</tex>, то мы имеем:

<tex>c^{-}(v) = |f| \sum\limits_{vu \in E} c_{vu}leqslant P_i</tex>.

для любого допустимого потока <tex>c^{+}(s) = +\inftyf</tex>. В частности, <tex>c^{-}(t) = +F \inftyleqslant P_i</tex>., таким образом получаем:

<tex>c(vl - 1) F \leqslant \displaystyle \sum_{i = min(c^{+1}(v), c^{l -1}(v))P_i \leqslant P</tex>.}}

{{Лемма|about = 2|statement=Пусть <tex> N </tex> {{---}} сеть, а <tex>f</tex> {{---}} допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>G_f</tex> равен общему потенциалу <tex>N</tex>.|proof=По [[Теорема_о_декомпозиции | теореме о декомпозиции]] поток можно разбить на множество простых путей из <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}(Guv) = \sum\limits_c(uv) - f_i</tex>, а <tex>c_{f_1}(wv) = c(wv) + f_i</tex>, сложив эти два значения, получим, что <tex>c^+(v \in V})</tex> остаётся неизменной. Применив такое же рассуждение для <tex>c^-(v)</tex>, получим, что потенциал каждой вершины остаётся неизменным.

|statement=Чило Число итераций [[Схема алгоритма Диница |алгоритма Диница]] в сети G <tex>N</tex> (<tex>s</tex> — исток, <tex>t</tex> — сток) с целочисленными пропускными способностями — <tex>O(\sqrt{P})</tex>.|proof=Пусть <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>O. После этого потребуется не больше <tex>\sqrt{P}</tex> фаз, чтобы найти максимальный поток. На предыдущей фазе поток (<tex>f</tex>) в <tex>N</tex> был не больше <tex>F-\sqrt{P}</tex>, таким образом <tex>F-|f| \geqslant \sqrt{cP}</tex>. <tex>G_f</tex> {{---}} сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому можно воспользоваться Леммой(1), чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>G_f</tex>, и получить оценку длины <tex>l</tex> слоистой сети: <tex>l \leqslant \dfrac{P}{F-|f|} + 1</tex> Так как каждая фаза увеличивает длину слоистой сети минимум на один, то осуществляется не больше <tex>\sqrt{P}</tex> фаз. Таким образом происходит не более <tex>2\sqrt{P}</tex> фаз.}} {{Лемма|about = 3|statement=Пусть в сети <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{\dfrac{2C}{F}} - 1</tex>.|proof=Обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множества <tex>X = \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|}{(Gl+1)}</tex> для <tex>0 \leqslant i \leqslant n</tex>, таким образом <tex>F \leqslant 2C\dfrac{|V|^2 }{ (l+1)^2}</tex>, из чего следует необходимое неравенство.}} {{Теорема|id=th2|about=Вторая теорема Карзанова|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>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| \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>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex> фаз, и <tex>O(C^{\frac{1}{3}}|V|^{\frac{2}{3}})</tex> фаз осталось.