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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Лемма:

Следующие утверждения эквивалентны: Поток [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]