Затем следующим образом изменяем вектор весов [я, Аг].

Для каждой вершины Xi из G, являющейся внешней вершиной дерева Т или содержащейся в псевдовершине из Т, помеченной как внешняя, уменьшаем Я; до Я; - Д.

Для каждой вершины Xi из G, являющейся внутренней вершиной дерева Т или содержащейся в псевдовершине из Т, помеченной как внутренняя, увеличиваем Я; до Я; + Д.

Для каждого множества вершин из G, образующих крайнюю псевдовершину в Т, помеченную как внешнюю, увеличиваем Кг до К + 2Д.

Для каждого множества вершин из G, образующих крайнюю псевдовершину из Т, помеченную как внутреннюю, уменьшаем Хг до Хг - 2 Д.

Безотносительно к значению Д все ребра из старого графа Gr, образующие текущее дерево Т, остаются в новом графе Gr, так как веса я,- всех внутренних и внешних вершин дерева Т увеличиваются и уменьшаются на одну и ту же величину, а значит равенство в выражении (12.17) по-прежнему сохраняется. Равенство в выражении (12.17) продолжает сохраняться и для всех ребер тех цветков, которые были срезаны, образовав псевдовершины графа Gy i. Таким образом, если псевдовершина из Gf-i была помечена как внешняя в альтернирующем дереве Т в старом графе Gf, то для некоторого ребра aj = {xt, х^), входящего в цветок, после срезания которого образовалась зта псевдовершина, веса Я; и Яь уменьшатся на Д. Но Хг для множества вершин Sr, соответствующего этой псевдовершине, увеличится на 2Д, так что равенство в выражении (12.17) по-прежнему сохранится для ребра uj. Аналогично обстоит дело для ребер тех цветков, которые порождают псевдовершины в G i, помеченные как внутренние вершины в дереве Т в старом графе Gf.

Предположим теперь, что в (12.22) Д = Д^ и что ребром, давшим это значение Д^ в (12.19), является df. После Д - изменения вектора весов [яг, К] - ребро а* будет удовлетворять соотношению (12.17), причем имеет место равенство, так что это ребро будет входить в новый граф Gr. Таким образом, используя а*, можно дерево Т (которое, как отмечалось выше, по-прежнему будет альтернирующим в новом графе Gr) либо расширить, либо сделать аугментальным в зависимости от того, является ли концевая взршина ребра а*, не принадлежащая дереву Т, экспонированной или нет.

Если в (12.22) Д = Да и а* - ребро, дающее это значение в (12.20), то добавление а* к дереву Т приведет к образованию цветка.

Наконец, если в (12.22) Д = Да, то вычитание величины 2 Д из в процессе изменения вектора весов [Яг, К] сделает в соответствии с (12.21) некоторое Хг (скажем, X*) равным нулю. Пусть

Остаток дерева

няя псевдовершина (а)

-Не в новом дереве

Рис. 12.15. (б) Внутренняя псевдовершина распускается и становится крайним цветком В*. (в) Образование нового дерева.

X* - внутренняя псевдовершина текущего дерева Г, соответствующая Я^, ш В* - крайний цветок, давший после срезания X*. Псевдовершина х* графа может теперь расцвести, образовав цветок В*, и это даст другой граф Gf-z. (Заметим, однако, что этот граф Gf-2 не будет тем же самым графом, из которого был получен граф после срезания цветка, так как распустившийся цветок, превративший Gj-y в G.j, не будет тем же самым крайним цветком, который после срезания дал Пусть Gt-y -

специальный остовный подграф нового графа G-j. Так как для всех ребер из fi* в (12.17) имеет место равенство, то очевидно.

ЧТО все эти ребра входят ив Gf-i. Если В* состоит, скажем, из 2q -\- i ребер, то в В* легко получить паросочетание из q ребер, как это показано на рис. 12.15. После того как цветок В* распустился, он разбивает текущее альтернирующее дерево на две компоненты, одна из которых касается цветка в вершине х^, а другая - в вершине Если использовать только ребра из В*, то можно указать две цепи (одну с четным и другую с нечетным числом ребер) между вершинами Xi vi х<. Добавляя ту цепь, у которой четное число ребер, к текущему дереву Т, связываем Т снова в одно дерево (см. рис. 12.15 (в)). Новое альтернирующее дерево можно затем расширять до тех пор, пока опять не возникнут приведенные выше случаи А, Б или В.

Алгоритм завершает работу, когда на некотором этане / в графе Gi будет получено совершенное паросочетание. Соответствующий граф Gf-i расширяется до начального графа G путем распускания цветков в порядке, обратном порядку их срезания, и построения паросочетании в каждом распустившемся цветке - так же, как на шаге 8 алгоритма ЗНПС из разд. 2.4.1.

Когда получено совершенное паросочетание, оно будет максимальным совершенным паросочетанием, так как тогда мы имеем решение (т. е. вектор [g]) и двойственный вектор весов [л,-, Яг], удовлетворяющий ограничениям (12.17) и (12.18), а также сформулированным выше условиям (i) и (ii).

Альтернативным случаем остановки является случай В, когда не существует никаких ограничений (12.19), (12.20) и (12.21). В этом случае А может быть взято как угодно большим, и совершенно очевидно, что в G не существует никакого совершенного паросочетания.

Приведенный выше метод решения ЗМП был предложен Эдмонд-сом [И]. Он является эффективным алгоритмом (см. разд. 3.3) и служит также конструктивным доказательством теоремы 5.

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

Присвоение начальных значений

Шаг 1. Присвоить вершинам графа G веса л так чтобы для всех ребер из G было выполнено соотношение (12.17), когда все К = 0. Взять G = Gq.

Формирование графа G

Шаг 2. Образовать специальный остовный подграф G текущего графа G.

Построение дерева

Шаг 3. Если в G не существует никакого альтернирующего дерева Т, то строить новое дерево с корнем в некоторой экспониро-