Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 32: Строка 32:
 
*<tex>\sum_{uv \in P_i} p(u,v)< 0 \Rightarrow P_i</tex> - цикл отрицательного веса. Противоречие.  
 
*<tex>\sum_{uv \in P_i} p(u,v)< 0 \Rightarrow P_i</tex> - цикл отрицательного веса. Противоречие.  
 
}}
 
}}
 +
 +
[[Категория: Задача о потоке минимальной стоимости]]

Версия 06:25, 27 декабря 2011

Лемма (об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети):
Следующие утверждения эквивалентны:
  • Поток [math] f [/math] — минимальной стоимости.
  • В остаточной сети [math] G_f [/math] нет циклов отрицательного веса.
Доказательство:
[math]\triangleright[/math]
  • [math]\Rightarrow [/math]

От противного. Пусть существует [math] C [/math] — цикл отрицательного веса в [math] G_f [/math], [math] c_m [/math] — наименьшая остаточная пропускная способность среди рёбер [math] C [/math].

Пустим по [math] C [/math] поток [math] f_+ = c_m [/math]. Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то [math] \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) \lt 0[/math]

[math]\Rightarrow [/math] [math]\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) \lt \sum_{u,v \in V} p(u,v) \cdot f[/math] [math]\Rightarrow f [/math] — не минимальный. Противоречие.

  • [math]\Leftarrow [/math]

От противного. Пусть [math] f [/math] - не минимальной стоимости. Тогда существует [math] f_m [/math] - поток минимальной стоимости и того же объема. Существует поток [math] f_- [/math], такой что [math]f_m = f + f_-~,~|f_-| = 0~,~\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) \lt 0[/math].

По теореме о декомпозиции [math] f_- [/math] представим в виде совокупности [math] P_i [/math], где поток [math]f_i[/math] ([math]f_-[/math] по [math]P_i[/math]) положителен и для каждого [math]i[/math] верно одно из двух утверждений:

  • [math] P_i [/math] - путь из истока в сток.
  • [math] P_i [/math] - цикл.

Если из истока в сток - изменится объем потока, что противоречит условию. [math]\Rightarrow \forall i~ P_i - [/math] цикл.

Так как все потоки по циклам положительны, [math] sgn(\sum_{u,v \in V} p(u,v)) = sgn(\sum_{u,v \in V} p(u,v) \cdot f_i(u,v))[/math]

Рассмотрим [math]P_i[/math]:

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