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

В действительности понимание роли отрицательных циклов в GM играет ключевую роль при анализе алгоритма. Сначала рассмотрим случай, в котором M является идеальным паросочетанием.

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

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

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

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

Доказательство. Предположим, утверждение ложно, и существует идеальное паросочетание M’ с меньшей стоимостью. Рассмотрим множество ребер, входящих в одно из паросочетаний M и M’ (но не в оба сразу).

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

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

В этом случае вычисление пути с минимальной стоимостью всегда будет однозначно определено; а при завершении с получением идеального паросочетания из (7.63) будет следовать, что паросочетание имеет минимальную стоимость.