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