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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
|statement=  
 
|statement=  
 
Следующие утверждения эквивалентны:
 
Следующие утверждения эквивалентны:
*Поток <math> f </math> {{---}} минимальной стоимости.
+
*Поток <tex> f </tex> {{---}} минимальной стоимости.
*В остаточной сети <math> G_f </math> нет циклов отрицательного веса.
+
*В остаточной сети <tex> G_f </tex> нет циклов отрицательного веса.
 
|proof=  
 
|proof=  
*<math>\Rightarrow </math>
+
*<tex>\Rightarrow </tex>
От противного. Пусть существует <math> C </math> {{---}} цикл отрицательного веса в <math> G_f </math>,
+
От противного. Пусть существует <tex> C </tex> {{---}} цикл отрицательного веса в <tex> G_f </tex>,
<math> c_m </math> {{---}} наименьшая остаточная пропускная способность среди рёбер <math> C </math>.
+
<tex> c_m </tex> {{---}} наименьшая остаточная пропускная способность среди рёбер <tex> C </tex>.
  
Пустим по <math> C </math> поток <math> f_+ = c_m </math>.  
+
Пустим по <tex> C </tex> поток <tex> f_+ = c_m </tex>.  
Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то <math> \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) < 0</math>  
+
Так как сумма весов по циклу отрицательна и поток по каждому ребру одинаков, то <tex> \sum_{u,v \in V} p(u,v) \cdot f_+(u,v) < 0</tex>  
 
 
<math>\Rightarrow </math> <math>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</math> <math>\Rightarrow f </math> {{---}} не минимальный. Противоречие.
 
  
 +
<tex>\Rightarrow </tex> <tex>\sum_{u,v \in V} p(u,v) \cdot (f + f_+)(u,v) < \sum_{u,v \in V} p(u,v) \cdot f</tex> <tex>\Rightarrow f </tex> {{---}} не минимальный. Противоречие.
 +
*<tex>\Leftarrow </tex>
 +
От противного. Пусть <tex> f </tex> - не минимальной стоимости. Тогда существует <tex> f_m </tex> - поток минимальной стоимости и того же объема.
 +
Существует поток <tex> f_- </tex>, такой что <tex> f_m = f + f_m</tex>.
 +
По сохранению потока <tex> f_- </tex> идёт по пути <tex> P </tex> и верно одно из двух утверждений:
 +
* <tex> P </tex> - из истока в сток.
 +
* <tex> P </tex> - цикл.
 +
Если из истока в сток - изменится объем потока, что противрочит условию.
 +
<tex>\Rightarrow P - цикл</tex>
 +
<tex>\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) < 0 \Rightarrow P</tex> - цикл отрицательного веса. Противоречие.
 
}}
 
}}

Версия 01:24, 16 января 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_m[/math]. По сохранению потока [math] f_- [/math] идёт по пути [math] P [/math] и верно одно из двух утверждений:

  • [math] P [/math] - из истока в сток.
  • [math] P [/math] - цикл.

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

[math]\sum_{u,v \in V} p(u,v) \cdot f_-(u,v) \lt 0 \Rightarrow P[/math] - цикл отрицательного веса. Противоречие.
[math]\triangleleft[/math]