Бюрократы, editor, Администраторы
422
правки
Изменения
Стоимости,а не веса
Следующие утверждения эквивалентны:
*Поток <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>\Rightarrow P - цикл</tex>
<tex>\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) < 0 \Rightarrow P</tex> - цикл отрицательного весаотрицательной стоимости. Противоречие.
}}
