Рис. 12.11г. Образовался цветок bj.

Рис. 12.Ид. Дерево после срезания цветка Ь^.

/>х,

Рис. 12.Ие. Образование цветка bj.

Рис. 12.Иж. Дерево после срезания 63.

Аугментальная цепь \

Рис. 12.113, Найдена аугментальная цепь.

его срезания возникает псевдовершина и образуется дерево, показанное на рис. 12.Ид. Рост дерева продолжается из вершины Xi3, но после добавления ребер (х^з, Хц), (х^, xg), (xs, xg), (15, Xij) опознается третий цветок (х^, х^, х^, х^ xv,), показанный на рис. 12. Ие. После его срезания возникает псевдовершина Ьз и образуется дерево, изображенное на рис. 12.Иж.

При следующем применении шага 3 добавляется ребро (63, Xia) и на шаге 4 обнаруживается аугментальная цепь {xi, х^, Ьз, Xia) (см. рис. 12.Из). Когда распускается 63 (см. рис. 12.Ни), то возможны две цепи от х^ к х^. Аугментальной цепью будет та цепь, которая состоит из нечетного числа ребер, т. е. = = {1, Xii, x-is, 15, Xl xg, Xi4, Xia). Когда ребра этой цепи, лежащие в паросочетании, меняются с теми, которые в нем не лежат, то получается новое улучшенное паросочетание, изображенное на рис. 12.12а.

Рис. 12.Пи. Цветок 63 распускается. - аугментальная цепь.

Рис. 12.12а. Улучшенное паросочетание.

Отбросив дерево ) и начиная с нового паросочетания, выберем на шаге 2 в качестве корня вершину Xjg. После нескольких применений шагов 3, 5 и 6 получается дерево, показанное на рис. 12.126, где имеет тот же самый смысл, что и ранее. На шаге 7 обнаруживается, что это дерево является венгерским. После его удаления остается подграф, изображенный на рис.12.13а.

На шаге 2 в качестве нового корня выбирается xq. После нескольких применений шагов 3 и 5 - сразу же после добавления ребер {Xig, х^ъ) и (xjB, Xge) на шаге 5 - обнаруживается аугментальная цепь. Окончательный вид дерева показан на рис. 12.13 б; аугментальной цепью является цепь (xgo, х^, xg, х^ъ, Xzg, Xj,). Поменяв ребра этой цепи, лежащие в паросочетаний на те, которые

ф qx,3 Корень

Рис. 12.126. Венгерское дерево в графе из (а).

) См. примечание 2 на стр. 382.- Прим.. ред.