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

Материал из Викиконспекты
Версия от 00:51, 16 января 2011; 192.168.0.2 (обсуждение) (Новая страница: «{{Лемма |about= об эквивалентности свойства потока быть минимальной стоимости и отсутствии о…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Лемма (об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети):
Следующие два утверждения эквивалентны:
  • [math] f [/math] - поток минимальной стоимости.
  • В остаточной сети [math] G_f [/math] нет циклов отрицательного веса.