Изменения
Нет описания правки
{{Определение
|definition=
<tex>c^{+}(v) = \sum\limits_{uv \in E} c_{uv}</tex>.
<tex>c^{-}(v) = \sum\limits_{vu \in E} c_{vu}</tex>.
<tex>p(v) = min\big\{c^{+}(sv), c^{-}(v) = +\inftybig\}</tex> - потенциал вершины <tex>v</tex>. Тогда общий потенциал выражается формулой:<tex>c^P = \sum\limits_{-v \in V, v \neq s,t}p(tv) </tex>.}} {{Лемма|statement= Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex> в сети с текущим потоком, равным 0, и максимальным потоком, равным <tex>F</tex>. Тогда <tex>l \leq \frac{P}{F} +1</tex> |proof=Пусть <tex>l</tex> - расстояние между <tex>s</tex> и <tex>t</tex>, а <tex>V_i</tex> - набор вершин, удаленных от <tex>s</tex> на <tex>i</tex> <tex>(i \inftyleq l)</tex>.<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>|f| \leq P_i</tex>
для любого допустимого потока <tex>c(v) = min(c^{+}(v)f</tex>. В частности, c^{-}(v))<tex>F \leq P_i</tex>., таким образом получаем:
<tex>c(Gl - 1) = F \leq \sumdisplaystyle \limits_sum_{v i = 1}^{l - 1} P_i \in V}c(v)leq P</tex> и лемма доказана.
}}
{{Лемма
|statement=
Пусть <tex>N</tex> - сеть, а <tex>f</tex> - допустимый поток в этой сети. Тогда общий потенциал в остаточной сети <tex>N(f)</tex> равен общему потенциалу <tex>N</tex>.
|proof=
}}
{{Теорема
