Изменения

|statement= Следующие утверждения эквивалентны:*Поток <tex> f </tex> {{---}} минимальной стоимости.*В среди потоков своей величины <tex> \iff </tex> в остаточной сети <tex> G_f </tex> нет циклов отрицательного весаотрицательной стоимости.

От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательного веса отрицательной стоимости в <tex> G_f </tex>,

Так как сумма весов стоимостей по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{(u,v ) \in VE} p(u,v) \cdot f_+(u,v) < 0</tex>

<tex>\Rightarrow </tex> <tex>\sum_{(u,v ) \in VE} p(u,v) \cdot (f + f_+)(u,v) < \sum_{(u,v ) \in VE} p(u,v) \cdot f(u, v)</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.

От противного. Пусть Рассмотрим поток <tex> f </tex> - не минимальной , такой что в <tex> G_f </tex> нет циклов отрицательной стоимости. Тогда существует Рассмотрим <tex> f_m f' </tex> {{- --}} поток величины <tex> |f| </tex> и минимальной стоимости и того же объема, т. е.Существует поток <tex> f_- p(f') \leqslant p(f) </tex>, такой что . По лемме представим <tex>f_m f' = f + f_-~,~|f_-| = 0~,~\sum_{u,v i} C_i </tex>. По условию стоимости всех циклов неотрицательны. Получаем <tex> p(f') \in V} geqslant p(u,vf) \cdot f_-Rightarrow p(f') = p(u,vf) < 0</tex>.}}

По [[Теорема_о_декомпозиции|теореме о декомпозиции]] <tex> f_- </tex> представим в виде совокупности <tex> P_i </tex>, где поток <tex>f_i</tex> (<tex>f_-</tex> по <tex>P_i</tex>) положителен и для каждого <tex>i</tex> верно одно из двух утверждений:* <tex> P_i </tex> - путь из истока в сток.* <tex> P_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(uRavindra Ahuja,v)= 0 \Rightarrow P_i</tex> - цикл нулевого веса. Тогда <tex>\exists j~:~P_j</tex> - цикл ненулевого веса.*<tex>\sum_{uv \in P_i} p(uThomas Magnanti,v)> 0 \Rightarrow P_i</tex> - цикл положительного весаJames Orlin. Рассмотрим <tex>f_* = Network flows (f_- - f_i1993)</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> - цикл отрицательного веса. Противоречие. }}