3.2. Пример

Мы хотим найти совершенное паросочетание для графа изображенного на рис. 12.16. Начнем с приписывания вершинам весов задаваемых вектором , и полагая все Веса выбраны нами довольно произвольно.

Специальный остовный подграф графа изображен на рис. 12.17. Пусть в качестве корня выбрана вершина

Рис. 12.16. Граф из примера 3.2.

на шаге 3 алгоритма строится альтернирующее дерево. На шаге 5 сразу же в паросочетание отбирается ребро Выбирая вершины (в указанном порядке) в качестве корней новых деревьев, немедленно получим аугментальные деревья и приходим к ситуации, в которой ребра в паросочетании показаны жирными линиями на рис. 12.17. Выбрав вершину в качестве корня нового дерева, строим это дерево на шаге 3 алгоритма до тех пор, пока не будет достигнуто состояние, изображенное на рис. 12.18, в котором образуется цветок. На шаге 4 этот цветок срезается и образуется псевдовершина а рост дерева продолжается на шаге 3, пока не достигается состояние, представленное на рис. 12.19, в котором дерево становится венгерским. Сам граф (после срезания) будет а его специальный остовный подграф — как показано соответственно на рис. 12.20 (а) и рис. 12.20 (б).

Рис. 12.17. Специальный остовный подграф

(кликните для просмотра скана)

Шаг 6 алгоритма дает

Таким образом,

После изменения весов новый вектор принимает вид , а вес соответствующий нечетному множеству вершин равен 2.

Рис. 12.20. (а) Граф G. (б) Граф G.

Для нового вектора весов новый специальный остовный подграф графа изображен на рис. 12.21; ребро входит в старый подграф

Так как дерево на рис. 12.19 сохраняется, то новое вошедшее ребро приводит к образованию цветка, состоящего из нечетного цикла Это сразу же обнаруживается на шаге 3, а на шаге 4 цветок срезается; возникает псевдовершина и получается новое дерево, показанное на рис. 12.22. Сам граф теперь будет а его специальный остовный подграф — эти графы представлены соответственно на рис. 12.23а и рис. 12.236.

Дерево, изображенное на рис. 12.22, является венгерским деревом в и на шаге 6 вычисляется новое значение для изменения

вектора весов:

Рис. 12.21. Новый специальный остовный подграф для графа из рис. 12.20(a).

Рис. 12.22. Альтернирующее дерево в из рис. 12.21.

Рис. 12.23. (а) Граф . (б) Граф

Следовательно, Используя это значение получаем , а вес соответствующий нечетному множеству вершин равен

Рис. 12.24. Новый специальный остовный подграф для графа из рис. 12.23(a).

Для этих новых весов новый специальный остовный подграф графа изображен на рис. 12.24. После введения нового ребра альтернирующее дерево на рис. 12.22 становится аугментальным, так что новое ребро входит в паросочетание. Это дерево «отбрасывается», и строится новое дерево с корнем в одной из оставшихся экспонированных вершин графа т. е. в вершине или В любом случае ребро сразу же попадает в паросочетание и получается совершенное паросочетание. Это совершенное паросочетание графа показано на рис. Чтобы найти соответствующее паросочетание в мы сначала распустим цветок и построим в нем совершенное паросочетание, как показано на рис. 12.25 (б), а затем распустим цветок и построим в нем совершенное паросочетание (см. рис. 12.25 (в)). На этом рисунке жирными линиями изображено максимальное совершенное паросочетание графа вес этого паросочетания равен 66. Так как в соответствии с теорией линейного программирования максимум величины из (12.11) равен минимуму величины и из (12.16), то можно сделать проверку. Поскольку тодх так что