Изменения
Нет описания правки
}}
==Теоремы==
{{Лемма
|about = 1
|proof=
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex> - набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(i \leq l)</tex>.
<tex>V_i</tex> - разъединяющее множество узлов: при его удалении исчезают все направлнные пути из <tex>s</tex> в <tex>t</tex>.
Следуя правилу сохранения потока, если <tex>f</tex> обозначить как любой допустимый поток, то <tex>|f|</tex> единиц потока должно проходить через <tex>V_i</tex>.
Но суммарное количество потока, которое может проходить через любую вершину не превосходит ее потенциала.
что и требовалось доказать.
}}
{{Теорема
|id=th1.
Пусть <tex>F</tex> - максимальный поток в сети <tex>N</tex>. Теорема верна для <tex>F \leq \sqrt{P}</tex>, так как после каждой фазы поток увеличивается хотя бы на 1. Если <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 \sqrt{P}</tex>.
<tex>N(f)</tex> - сеть с максимальным потоком <tex>F-|f|</tex> и потенциалом <tex>P</tex> (по Лемме(2)). Поэтому мы можем использовать Лемму(1) чтобы оценить расстояние между <tex>s</tex> и <tex>t</tex> в <tex>N(f)</tex>. Отсюда получаем , и получить оценку длины (<tex>l</tex>) слоистой сети:
<tex>l \leq \frac{P}{F-|f|} + 1</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>.
|proof=
Если <tex>F \leq C^{1/3}|V|^{2/3}</tex>, то теорема очевидна.
Положим, что <tex>F > 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>F - |f| \ge C^{1/3}|V|^{2/3}</tex>. Мы можем применить Лемму(2), чтобы оценить длину <tex>l</tex> слоистой сети, и, соответственно, количество выполненных фаз:
<tex>l \leq |V|{(\frac{2C}{F-|f|})}^{1/2} - 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]
