Изменения
Нет описания правки
==Определения==
{{Определение
|definition=
Обозначим длину слоистой сети <tex>l</tex> - как длину кратчайшего <tex>s-t</tex> пути в <tex>N(f)</tex>.
}}
==Теоремы==
Идея доказательства следующая. Сперва мы
получим оценку длины слоистой сети с точки зрения величины максимального потока и другого интересующего нас
параметра(здесь мы рассматриваем P и C).Эта оценка будет возрастающей функцией интересующего параметра
и убывающей функцией от максимального потока. Мы разобьем вычисление максимального потока на 2 части.
В первой мы предполагаем, что поток достиг величины, находящейся в пределах <tex>\bar{F}</tex> от оптимального. Таким образом, потребуется
не больше <tex>\bar{F}</tex> дополнительных фаз перед завершением. В этом и состоит вторая часть вычислений. Теперь используем
оценку длины слоистой сети чтобы опредлить предел количества фаз, осуществляемых в 1 части.
<tex>\bar{F}</tex> выбрано так, что оно такого же порядка, что и длина слоистой сети в конце 1 части вычислений.
Таким образов количество фаз <tex>O(\bar{F})</tex>.
{{Лемма
Так как каждая фаза увеличивает длину слоистой сети минимум на один, то осуществляется не больше <tex>\sqrt{P}</tex> фаз. Таким образом происходит не более <tex>2\sqrt{P}</tex> фаз.
}}
{{Лемма
|about = 3
|statement=
Пусть в сети <tex>N</tex> нет параллельных ребер. <tex>f</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 |V|\sqrt{\frac{2C}{F}} - 1</tex>.
|proof=
Как и раньше, обозначим <tex>V_i</tex> как набор вершин на расстоянии <tex>i</tex> от <tex>s</tex>. Множество <tex>X = \bigcup_{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 2C|V_k||V_{k+1}|</tex>.
Таким образом <tex>F</tex> ограничен наименьшим из <tex>|V_k||V_{k+1}|</tex>. Но этот минимум максимизируется, когда <tex>|V_i| = |V|/(l+1)</tex> для <tex>0 \leq i \leq n</tex>, таким образом <tex>F \leq 2C|V|^2(l+1)^2</tex>. Выражая <tex>l</tex> получаем нужное.
}}
|id=th2
|about=Вторая теорема Карзанова
|statement=Число итераций алгоритма Диница в сети с целочисленными пропускными способностями - <tex>GO(C^{1/3}|V|^{2/3})</tex> (.|proof=Если <tex>sF \leq C^{1/3}|V|^{2/3}</tex>, то теорема очевидна. Положим, что <tex>tF > C^{1/3}|V|^{2/3}</tex> - исток , и стокрассотрим последнбб фазу, соответственнов которой поток <tex>f</tex> не превышает <tex>F - C^{1/3}|V|^{2/3}</tex>.В этот момент осталось не более <tex>C^{1/3}|V|^{2/3} + 1</tex> фаз, и <tex>N(f) </tex> - сеть с целочисленными пропускными способностями меньше максимальным потоком <tex>c_F - |f| \ge C^{1/3}|V|^{max2/3}</tex> . Мы можем применить Лемму(2), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз: <tex>l \leq |V|{(\frac{2C}{F-|f|})}^{1/2} - 1 </tex> <tex>O(\sqrt[leq 2^{1/2}C^{1/3]}|V|^{2/3} - 1</tex>. Таким образом, прошло <tex>O(C^{1/3}|V|^{2/3})</tex> фаз, и <tex>O(C^2 c_{max1/3}|V|^{2/3})</tex>фаз осталось. Теорема доказана.
}}
