105
правок
Изменения
м
Нет описания правки
<tex>V_i</tex> {{---}} разъединяющее множество узлов: при его удалении исчезают все пути из <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> 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}(uv) = c(uv) - f_i</tex>, а <tex>c_{f_1}(wv) = c(wv) + f_i</tex>, сложив эти два значения, получим, что <tex>c^+(v)</tex> остается остаётся неизменной. Применив такое же рассуждение для <tex>c^-(v)</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|}{(l+1)}</tex> для <tex>0 \leqslant i \leqslant n</tex>, таким образом <tex>F \leqslant 2C\dfrac{|V|^2 }{ (l+1)^2}</tex>, из чего следует необходимое неравенство.
}}
