Просмотр исходного текста страницы Лемма об эквивалентности свойства-потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети

{{Лемма
|statement= 
Следующие утверждения эквивалентны:
*Поток <tex> f </tex> {{---}} минимальной стоимости.
*В остаточной сети <tex> G_f </tex> нет циклов отрицательного веса.
|proof= 
*<tex>\Rightarrow </tex>
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательного веса в <tex> G_f </tex>,
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.

Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>. 
Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) < 0</tex> 

<tex>\Rightarrow </tex> <tex>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.
*<tex>\Leftarrow </tex>
От противного. Пусть <tex> f </tex> - не минимальной стоимости. Тогда существует <tex> f_m </tex> - поток минимальной стоимости и того же объема.
Существует поток <tex> f_- </tex>, такой что <tex> f_m = f + f_m</tex>.
По сохранению потока <tex> f_- </tex> идёт по пути <tex> P </tex> и верно одно из двух утверждений:
* <tex> P </tex> - из истока в сток.
* <tex> P </tex> - цикл.
Если из истока в сток - изменится объем потока, что противрочит условию.
<tex>\Rightarrow P - цикл</tex> 
<tex>\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) < 0 \Rightarrow P</tex> - цикл отрицательного веса. Противоречие. 
}}