2.5. Пример

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

На шаге 2 алгоритма в качестве корня выбирается вершина и после нескольких применений шагов 3 и 5 получается альтернирующее дерево, изображенное на рис. 12.116. На этой стадии сразу же после добавления ребер и к альтернирующему дереву шаг 6 опознает цветок дающий после срезания псевдовершину и приводит к дереву, изображенному на рис. 12.11в.

Следующее применение шага 3 добавляет ребра (на самом деле как показано на рис. 12.11 г. Второй цветок опознается на шаге 6. После

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

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

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

его срезания возникает псевдовершина и образуется дерево, показанное на рис. 12.11д. Рост дерева продолжается из вершины но после добавления ребер опознается третий цветок показанный на рис. 12. Не. После его срезания возникает псевдовершина и образуется дерево, изображенное на рис. 12.11ж.

При следующем применении шага 3 добавляется ребро и на шаге 4 обнаруживается аугментальная цепь (см. рис. 12.11з). Когда распускается (см. рис. 12.11и), то возможны две цепи от Аугментальной цепью будет та цепь, которая состоит из нечетного числа ребер, т. е. Когда ребра этой цепи, лежащие в паросочетании, «меняются» с теми, которые в нем не лежат, то получается новое улучшенное паросочетание, изображенное на рис. 12.12а.

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

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

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

На шаге 2 в качестве нового корня выбирается После нескольких применений шагов 3 и 5 — сразу же после добавления ребер на шаге 5 — обнаруживается аугментальная цепь. Окончательный вид дерева показан на рис. 12.13 б; аугментальной цепью является цепь «Поменяв» ребра зтой цепи, лежащие в паросочетании на те, которые

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

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

Рис. 12.14. Наибольшее паросочетание в примере 2.5.

в нем не лежат, получим паросочетание, не оставляющее никаких экспозированных вершин. (Заметим, что вершина удалена ранее вместе с венгерским деревом.) Получающееся паросочетание, изображенное на рис. 12.14, будет, таким образом, наибольшим паросочетанием.