Изменения
Нет описания правки
Следующие утверждения эквивалентны:
*Поток <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> f </tex> - не минимальной стоимости. Тогда существует <tex> f_m </tex> - поток минимальной стоимости и того же объема.
Существует поток <tex> f_- </tex>, такой что <tex> f_m = f + f_-</tex>.
По сохранению потока [[Теорема_о_декомпозиции|теореме о декомпозиции]] <tex> f_- </tex> идёт по пути представим в виде совокупности <tex> P P_i </tex> и , где для каждого i верно одно из двух утверждений:* <tex> P P_i </tex> - путь из истока в сток.* <tex> P P_i </tex> - цикл.Если из истока в сток - изменится объем потока, что противрочит противоречит условию.<tex>\Rightarrow P \forall i P_i - цикл</tex> цикл. <tex>\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) < 0 \Rightarrow PP_i</tex> - цикл отрицательной стоимостиотрицательного веса. Противоречие.
}}
