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

{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
|+
|-align="center"
|'''НЕТ ВОЙНЕ'''
|-style="font-size: 16px;"
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

''Антивоенный комитет России''
|-style="font-size: 16px;"
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|-style="font-size: 16px;"
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
|}

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

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

<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> - цикл отрицательного веса. Противоречие. 
}}