2.4. Алгоритм для ЗНПС

Пусть задано начальное паросочетание. (Допустимо использование цустого паросочетания.) Алгоритм осуществляет систематический поиск аугментальных цепей с целью улучшения заданного паросочетания в соответствии с теоремой 1. Алгоритм был предложен Эдмондсом [10, 11].

Альтернирующее дерево имеет своим корнем некоторую экспонированную вершину и строится путем попеременного добавления

ребер, лежащих и не лежащих в паросочетании, до тех пор, пока или

(I) дерево станет аугментальным, или

(II) на дереве появится цветок, или

(III) дерево станет венгерским.

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

В случае (II) обнаруживается получившийся цветок (как описано в разд. 2.2), срезается и продолжается рост дерева в процессе поиска аугментальной цепи. Что касается вычислительной стороны, то срезание не производится «явным образом». Достаточно пометить все вершины цветка как внешние и отметить, что все они принадлежат этому цветку. Порядок, в котором цветки «срезаются», важен, так как в конце всей процедуры цветки должны «расцвести» в обратном порядке.

В случае (III) вершины венгерского дерева и инцидентные им ребра совсем удаляются из графа (в соответствии с теоремой 4) и алгоритм применяется к оставшемуся подграфу.

2.4.1. Описание алгоритма

Начальная установка.

Шаг 1. Выбрать в начальное паросочетание

Выбор корня.

Шаг 2. Если в существуют по крайней мере две экспонированные вершины, то взять одну из них в качестве корня; в противном случае перейти к шагу 8.

Шаг 3. Взять внешнюю вершину дерева. Для каждого ребра если экспонированная вершина, то перейти к шагу 4; если внутренняя вершина, то перейти к шагу 7; если не принадлежит дереву и не является экспонированной, то перейти к шагу 5.

Шаг 4. Найдена аугментальная цепь из корня к Построить новое улучшенное паросочетание, удаляя текущее дерево и пометки вершин, и перейти к шагу 2.

Шаг 5. Добавить к альтернирующему дереву ребро и отметить вершину как внутреннюю. Найти ребро принадлежащее текущему паросочетанию, и добавить его к дереву, пометив вершину как внешнюю. Если существует ребро между и другой внешней вершиной, то перейти к шагу 6. В противном: случае перейти к шагу 3.

Шаг 6. Опознать и срезать получившийся цветок. Отметить возникшую псевдовершину как внешнюю. Внести поправку в частичное упорядочение цветков и возвратиться к шагу 3.

Шаг 7. Возвращаться к шагу 3 до тех пор, пока единственным возникающим случаем не будет случай Тогда удалить все вершины дерева и все ребра из инцидентные этим вершинам. Считать оставшийся подграф графом и вернуться к шагу 2

Шаг 8. Выделить отдельно в последнем графе каждом удаленном венгерском графе оптимальное паросочетание, поступая так. Распустить сначала крайний цветок и выделить паросочетание, которое оставляет экспонированной относительно него ту вершину которая входит в паросочетание в нераспустившемся цветке. (См. теорему 2.) Продолжать процесс распускания в порядке, обратном к установленному на шаге 6, до тех пор, пока весь граф не будет распустившимся и не будет получено наибольшее паросочетание.