Цены и узлы

Будет полезно представить, что с каждым узлом v связана числовая цена p(v). Цены помогут не только лучше понять логику работы алгоритма, но и ускорить его реализацию.

Чтобы понять, как работают цены в данном случае, полезно представить их экономическую интерпретацию.

Рассмотрим следующий сценарий: допустим, множество X представляет людей, которые назначаются на работы из множества Y. Для ребра e = (x,y) стоимость ce представляет затраты на выполнение человеком x работы y.

Цену p(x) можно сравнить с премией, которая выплачивается человеку x за участие в этой системе — своего рода «поощрительная премия».

С учетом этого обстоятельства затраты на назначение человека x на работу y возрастают до p(x) + ce. С другой стороны, цена p(y) для узлов y Ѯ Y может рассматриваться как выгода от выполнения работы y (кто бы из работников X ее ни выполнял).

В этом случае «чистые затраты» на назначение человека x на работу y принимают вид p(x) + ce − p(y): стоимость найма работника x с премией p(x), выполнение им работы y с затратами ce, с получением выгоды p(y).

Назовем эту величину сокращенной стоимостью ребра e = (x, y), и обозначим ее cpe = p(x) + ce − p(y). Однако важно помнить, что в описание задачи входят только стоимости ce; цены (премии и выгоды) всего лишь помогают анализировать решение.

Набор чисел {p(v) : v Ѯ V} образует множество совместимых цен по отношению к паросочетанию M, если:

• для всех непарных узлов x Ѯ X p(x) = 0 (если человеку не предложена работа, то и платить ему не нужно);
• для всех ребер e = (x, y) p(x) + ce ≥ p(y) (каждое ребро имеет неотрицательную сокращенную стоимость); и
• для всех ребер e = (x, y) Ѯ M p(x) + ce = p(y) (каждое ребро, используемое при назначении, имеет сокращенную стоимость 0).

Чем полезна такая система цен? На интуитивном уровне совместимые цены предполагают, что паросочетание имеет малую стоимость: по парным ребрам премия равна стоимости а на всех остальных ребрах премия не превышает стоимость.

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

Однако мы утверждаем, что если M является произвольным паросочетанием, для которого существует множество совместимых цен, то GM не содержит отрицательных циклов. Для идеального паросочетания M из этого будет следовать, что M имеет минимальную стоимость согласно (7.63).