Анализ отрицательных циклов

В действительности понимание роли отрицательных циклов в GM играет ключевую роль при анализе алгоритма. Сначала рассмотрим случай, в котором M является идеальным паросочетанием. Обратите внимание: в этом случае узел 5 не имеет вы- ходящих ребер, а t не имеет входящих ребер в GM (поскольку паросочетание явля- ется идеальным), а следовательно, никакой цикл в GM не может содержать 5 или t.

(7.62) Имеется идеальное паросочетание M. Если в GM существует направлен- ный цикл C с отрицательной стоимостью, то стоимость M не минимальна.

Доказательство. Воспользуемся циклом C для увеличения — подобно тому, как направленные пути использовались для получения паросочетаний с большим размером. Увеличение M относительно C подразумевает добавление (и удаление) ребер из C в M. Полученное новое идеальное паросочетание M' имеет стоимость cost(M') = cost(M) + cost(C); однако cost(C) < 0, а следовательно, стоимость M не минимальна. ■

Что еще важнее, обратное утверждение также истинно; таким образом, идеаль- ное паросочетание M имеет минимальную стоимость тогда и только тогда, когда в GM нет отрицательных циклов.

(7.63) Пусть M — идеальное паросочетание. Если в GM нет направленных циклов с отрицательной стоимости C, то M является идеальным паросочетанием с минимальной стоимостью.

Доказательство. Предположим, утверждение ложно, и существует идеальное паросочетание M' с меньшей стоимостью. Рассмотрим множество ребер, входящих в одно из паросочетаний M и M' (но не в оба сразу). Заметим, что такое множе- ство ребер соответствует множеству направленных циклов в GM, непересекаю- щихся по узлам. Стоимость множества направленных циклов равна в точности cost(M') - cost(M). Если M' имеет меньшую стоимость, чем M, значит, по крайней мере один из таких циклов имеет отрицательную стоимость. ■

Итак, план заключается в переборе паросочетаний увеличивающегося размера, при котором граф GM не содержит отрицательных циклов ни на одной итерации. В этом случае вычисление пути с минимальной стоимостью всегда будет одно- значно определено; а при завершении с получением идеального паросочетания из

(7.63) будет следовать, что паросочетание имеет минимальную стоимость.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Анализ отрицательных циклов:

  1. Наложение циклов
  2. Наложение циклов
  3. ОТРИЦАТЕЛЬНАЯ ИНФЕКЦИЯ
  4. Положительное и отрицательное
  5. Положительное и отрицательное
  6. Положительное и отрицательное Ки
  7. 4.10. ОТРИЦАТЕЛЬНАЯ ОБРАТНАЯ СВЯЗЬ
  8. 4.13. ПРЕОДОЛЕНИЕ ОТРИЦАТЕЛЬНОЙ СВЯЗИ
  9. Глава 11 Освобождение от отрицательных эмоций
  10. ПЕРЕНЕСЕНИЕ ОТРИЦАТЕЛЬНОЕ
  11. Отрицательная энергия растворяется в воде.
  12. Примеры отрицательных инфекций:
  13. Глава 2 Отрицательное и положительное программирование
  14. 3. Отрицательные предсказания относительно меня.
  15. Отрицательные стороны синхронных игр
  16. Отрицательные стороны борьбы с ревностью
  17. Отрицательные стороны метода договора
  18. Этюды на отображение отрицательных черт характера
  19. § 3. АБСОЛЮТИЗАЦИЯ ФОРМ ПРОЯВЛЕНИЯ СУЩНОСТИ И ЕЕ ОТРИЦАТЕЛЬНЫЕ ПОСЛЕДСТВИЯ