Изменения

Рассмотрим поток <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>.

}}

[[Категория: Задача о потоке минимальной стоимости]]