16
правок
Изменения
Нет описания правки
|statement=
Следующие утверждения эквивалентны:
*Поток <mathtex> f </mathtex> {{---}} минимальной стоимости.*В остаточной сети <mathtex> G_f </mathtex> нет циклов отрицательного веса.
|proof=
*<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> <math>\Rightarrow </math> <math>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</math> <math>\Rightarrow f </math> {{---}} не минимальный. Противоречие.
<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> - цикл отрицательного веса. Противоречие.
}}
