Изменения

Существует поток <tex> f_- </tex>, такой что <tex> f_m = f + f_-~,~|f_-| = 0~,~\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) < 0</tex>. По [[Теорема_о_декомпозиции|теореме о декомпозиции]] <tex> f_- </tex> представим в виде совокупности <tex> P_i </tex>, где поток <tex>f_i</tex> (<tex>f_-</tex> по <tex>P_i</tex>) положителен и для каждого <tex>i </tex> верно одно из двух утверждений:

<tex>\Rightarrow \forall i ~ P_i - </tex> цикл. Так как все потоки по циклам положительны, <tex> sgn(\sum_{u,v \in V} p(u,v)) = sgn(\sum_{u,v \in V} p(u,v) \cdot f_i(u,v))</tex>

Рассмотрим <tex>P_i</tex>:*<tex>\sum_{uv \in P_i} p(u,v )= 0 \Rightarrow P_i</tex> - цикл нулевого веса. Тогда <tex>\exists j~:~P_j</tex> - цикл ненулевого веса.*<tex>\sum_{uv \in VP_i} p(u,v) > 0 \cdot Rightarrow P_i</tex> - цикл положительного веса. Рассмотрим <tex>f_* = (f_- - f_i)</tex>. Стоимость <tex>f_*</tex> меньше стоимости <tex>f_-</tex> <tex>\Rightarrow f_m</tex> - не минимальной стоимости. Противоречие.*<tex>\sum_{uv \in P_i} p(u,v) < 0 \Rightarrow P_i</tex> - цикл отрицательного веса. Противоречие.