Изменения
Новая страница: «{{Лемма |statement= Следующие утверждения эквивалентны: *Поток <math> f </math> {{---}} минимальной стоим…»
{{Лемма
|statement=
Следующие утверждения эквивалентны:
*Поток <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> {{---}} не минимальный. Противоречие.
}}
|statement=
Следующие утверждения эквивалентны:
*Поток <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> {{---}} не минимальный. Противоречие.
}}
