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

Материал из Викиконспекты
Перейти к: навигация, поиск
Лемма (об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети):
Следующие два утверждения эквивалентны:
  • [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]\triangleleft[/math]