Изменения

|statement=Следующие два утверждения эквивалентны:* Поток <mathtex> f </mathtex> {{- поток --}} минимальной стоимости.* В остаточной сети <mathtex> G_f </mathtex> нет циклов отрицательного веса.

*<mathtex>\Rightarrow </mathtex>От противного. Пусть существует <mathtex> C </mathtex> {{---}} цикл отрицательного веса в <mathtex> G_f </mathtex>,<mathtex> c_m </mathtex> {{---}} наименьшая остаточная пропускная способность среди рёбер <mathtex> C </mathtex>.

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

<mathtex>\Rightarrow </mathtex> <mathtex>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</mathtex> <mathtex>\Rightarrow f </mathtex> {{---}} не минимальный. Противоречие.*<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> - цикл отрицательного веса. Противоречие.