147
правок
Изменения
Нет описания правки
По [[Теорема о декомпозиции|теореме о декомпозиции]] <tex> g - f</tex> можно представить как сумму элементарных потоков вдоль путей <tex>P_i : s \leadsto t</tex> и циклов <tex>C_i</tex>. В этом представлении нет отрицательных циклов, иначе прибавление его к <tex> f </tex> даст поток меньшей стоимости. Если есть положительный цикл, то вычтем его из <tex> g </tex> и получим поток меньшей стоимости. Таким образом, <tex>p(C_i) = 0</tex> для всех циклов.
Тогда <tex>p(g - f) = \sum\limits_{P_i} p(P_i)\cdot c_f(P_i) \geq geqslant p(P) \cdot \sum\limits_{P_i}c_f(P_i) \ge geqslant p(P) \cdot \delta</tex>.
Отсюда <tex> p(g) \ge geqslant p(f) + p(P) \cdot \delta \ge geqslant p(g) </tex> и поток <tex>f + \delta \cdot f_P</tex> {{---}} минимальный.
}}
