Изменения
Нет описания правки
<tex>\Rightarrow </tex> <tex>\sum_{(u,v) \in E} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v) \in E} p(u,v) \cdot f</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.
*<tex>\Leftarrow </tex>
Рассмотрим поток <tex> f </tex>: в <tex> G_f </tex> нет циклов отрицательной стоимости. Рассмотрим <tex> f' </tex> - поток минимальной стоимости, т. е. <tex> p(f') <= p(f) </tex>. По лемме представим <tex>f' = f + \sum_{i} C_i </tex>. По условию стоимости всех циклов не отрицательнынеотрицательны. Получаем <tex> p(f') >= p(f) \Rightarrow p(f') = p(f)</tex>.
}}
