ванной вершине из G. Если экспонированных вершин нет, перейти к шагу 8. Если в G уже существует альтернирующее дерево, то продолжать его построение. Если на Т обнаружится цветок, то перейти к шагу 4. Если дерево Т станет аугментальным, то перейти к шагу 5.

Если дерево Т станет венгерским, то перейти к шагу 6.

Цветки на дереве

Шаг 4. Срезать цветки и образовать псевдовершину. Обозначим получившийся граф через G, его специальный остовный подграф через G, а оставшееся дерево через Т. Перейти к шагу 3.

Аугменталъное дерево

Шаг 5. Улучшить текущее паросочетание, поменяв вдоль аугментальной цепи ребра, принадлежащие паросочетанию и ему не принадлежащие. Отбросить дерево Т и перейти к шагу 3.

Венгерское дерево

Шаг 6. Вычислить Л^, Лг, Лз и А по формулам (12.19) - (12.22). Если нет никаких ограничений (12.19) - (12.21), то остановиться; в графе нет совершенного паросочетания. В противном случае изменить вектор весов [я Яг], как описано выше. Если А = Al или А = Aj, то сохранить текущее дерево Т и перейти к шагу 2. Если А = Аз, то перейти к шагу 7.

Шаг 7. Распустить псевдовершину, давшую Аз в соотношении (12.21), в цветок В. Обозначим получившийся граф через G, а его специальный остовный подграф через G. Построить в В совершенное паросочетание. Перестроить альтернирующее дерево, добавляя к ребрам из Т необходимую цепь из В, и обозначить это дерево символом Т. Перейти к шагу 3.

Конец

Шаг 8. Распустить все цветки в обратном порядке (к первоначальному порядку срезания цветков), находя совершенное паросочетание после каждого распускания.

3 2. Пример

Мы хотим найти совершенное паросочетание для графа Gq, изображенного на рис. 12.16. Начнем с приписывания вершинам Xi, i = 1, . . ., 12, весов Я;, задаваемых вектором [я;]= (9, 2, И, 7, 3, 4, 8, 6,6, 5,3, 4), и полагая все К=0. Веса Я; выбраны нами довольно произвольно.

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

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

на шаге 3 алгоритма строится альтернирующее дерево. На шаге 5 сразу же в паросочетание отбирается ребро {xi, Xg). Выбирая вершины Хз, Xs и Х7 (в указанном порядке) в качестве корней новых деревьев, немедленно получим аугментальные деревья и приходим к ситуации, в которой ребра в паросочетании показаны жирными линиями на рис. 12.17. Выбрав вершину Xjg в качестве корня нового дерева, строим это дерево на шаге 3 алгоритма до тех пор, пока не будет достигнуто состояние, изображенное на рис. 12.18, в котором образуется цветок. На шаге 4 этот цветок срезается и образуется псевдовершина Xbj, а рост дерева продолжается на шаге 3, пока не достигается состояние, представленное на рис. 12.19, в котором дерево становится венгерским. Сам граф (после срезания) будет G, а его специальный остовный подграф - GI, как показано соответственно на рис. 12.20 (а) и рис. 12.20 (б).

12 ЙДГ„

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

Корень I*

Рис. 12.18. Альтернирующее дерево в G[. Корень.

Соответствует множеству

Рис. 12.19. Венгерское дерево в GJ.