Изменения
→Корректность
{{Определение
|definition='''Приведенной стоимостью''' (англ. ''reduced cost'') ребра назовем следующую величину: <tex>p_{\varphi}(uv)=\varphi(u) + p(uv) - \varphi(v)</tex>.}}
Иными словами, приведенная стоимость {{---}} это сколько нужно потратить денег, чтобы перевести единицу жидкости из <tex>u</tex> в <tex>v</tex>. (Ее нужно купить в <tex>u</tex>, перевезти из <tex>u</tex> в <tex>v</tex> и продать в <tex>v</tex>.)
{{Лемма
|statement=Если <tex>f</tex> {{---}} поток минимальной стоимости, то <tex>\exists \varphi</tex> такое, что <tex>\forall uv: \; c_{f}(uv) > 0 \qquad p_{\varphi}(uv) \geqslant 0</tex>
|proof=
:Рассмотрим [[Дополняющая сеть, дополняющий путь|остаточную сеть]] {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети</ref>}}
===Сложность===
