Изменения
Нет описания правки
Тогда общий потенциал выражается формулой:
<tex>P = \sum\limits_{v \in V, v \neq s,t}p(v)</tex>.
Остаточную сеть обозначим <tex>N(f)</tex>.
Обозначим длину слоистой сети <tex>l</tex> - как длину кратчайшего <tex>s-t</tex> пути в N(f).
}}
|about = 1
|statement=
Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex> в слоистой сети с текущим потоком, равным 0, и максимальным потоком, равным <tex>F</tex>.
Тогда <tex>l \leq \frac{P}{F} + 1</tex>
Пусть <tex>c_f</tex> - функция пропускных способностей в <tex>N(f)</tex>, а <tex>p_f(v), in_f(v), out_f(v)</tex> - потенциал, множество входящих ребер и множество выходящих ребер вершины <tex>v</tex> из <tex>N(f)</tex>.
Достаточно доказать, что <tex>p_f(v) = p(v)</tex>. Ребру <tex>e</tex> из <tex>in(v)</tex> соответствуют ребро <tex>e_1</tex> из <tex>in_f(v)</tex> с пропускной способностью <tex>c(e) - f(e)</tex>, и ребро <tex>e_2</tex> из <tex>out_fout(v)</tex> с пропускной способностью <tex>f(e)</tex>. Аналогично, ребру <tex>e</tex> из <tex>out(v)</tex> соответствуют ребра из <tex>out_f(v)</tex> с пропускной способностью <tex>c(v) - f (v)</tex> и <tex>in_f(v)</tex> с пропускной способностью <tex>f(e)</tex>. Используя правило сохранения потока, нетрудно проверить, что
<tex>\displaystyle\sum_{e\in in_f(v)} c_f(e) = \sum_{e\in in(v)}c(e)</tex>
|statement=Число итераций алгоритма Диница в сети <tex>N</tex> (<tex>s</tex>, <tex>t</tex> - исток и сток, соответственно.) с целочисленными пропускными способностями - <tex>O(\sqrt{P})</tex>.
|proof=
Пусть <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>
Так как каждая фаза увеличивает длину слоистой сети минимум на один,то осуществляется не больше <tex>\sqrt{P}</tex> фаз. Таким образом происходит не более <tex>2\sqrt{P}</tex> фаз.
}}
