3.1. Алгоритм для ЗМП

Предположим, что мы начинаем с графа Присвоим его вершинам веса выбирая величины достаточно большими, чтобы ограничения (12.17) выполнялись, когда все взяты равными нулю. Пусть теперь остовный подграф в содержащий только те ребра, для которых в (12.17) имеет место равенство. Назовем специальным остовным подграфом графа Если в можно найти совершенное паросочетание (с помощью алгоритма для описанного в предыдущем разделе), то это паросочетание — оптимальное. Действительно, вектор удовлетворяет ограничениям (12.17) и (12.18), условие (i) выполнено автоматически, так как для всех а условие (ii) выполнено ввиду того, что в паросочетание входят только ребра из так что ; не может быть если не удовлетворяет ограничению (12.17).

Вообще говоря, может оказаться, что в совершенное паросочетание найти нельзя, а алгоритм для ЗНПС обнаружит венгерское дерево. Как уже отмечалось в разд. 2.3, наибольшее

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

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

Для более ясного понимания алгоритма мы введем следующую индексацию. Первоначальный граф будет обозначаться через Специальный остовный подграф графа есть в этом графе строится альтернирующее дерево, как это делалось в алгоритме для Когда, наконец, образуется и срезается первый цветок, сам граф будет обозначаться через а его специальный остовный подграф — через После срезания цветков граф будет обозначен символом а его специальный остовный подграф —

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

A) на дереве появится цветок;

Б) дерево станет аугментальным;

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

Случай А. В этом случае цветок срезается, получается новый граф и его специальный остовный подграф Как отмечалось выше, срезание цветка приводит к дереву с корректной структурой альтернирующего дерева, так что можно сохранить и продолжать процесс роста дерева.

Случай Б. В этом случае, как уже объяснялось для получается улучшенное паросочетание — с большим числом ребер.

Дерево следует отбросить и, взяв в графе оставшуюся экспонированную вершину, приступить к построению нового дерева с корнем в этой вершине. Здесь следует заметить, что как только отброшено и в G} «начинает расти новое дерево», некоторые из псевдовершин в (образованные после срезания более ранних цветков, давших графы могут оказаться помеченными как внутренние в новом дереве.

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

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

(б) текущее альтернирующее дерево в старом графе можно было строить дальше, или на нем возникнет цветок, или оно станет аугментальным — с использованием новых ребер, входящих в новый граф

либо некоторая псевдовершина в текущем альтернирующем дереве, помеченная как внутренняя, перестанет быть таковой;

либо будет доказано, что в нет совершенного паросочетания.

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

Для ребер из не принадлежащих обе концевые вершины которых лежат в и обе помечены как внешние, находим

Для множеств вершин из образующих крайние псевдовершины в и помеченных как внутренние, находим

Берем

Затем следующим образом изменяем вектор весов

Для каждой вершины из являющейся внешней вершиной дерева или содержащейся в псевдовершине из помеченной как внешняя, уменьшаем до

Для каждой вершины из являющейся внутренней вершиной дерева или содержащейся в псевдовершине из помеченной как внутренняя, увеличиваем до

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

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

Безотносительно к значению все ребра из старого графа образующие текущее дерево остаются в новом графе так как веса всех внутренних и внешних вершин дерева увеличиваются и уменьшаются на одну и ту же величину, а значит равенство в выражении (12.17) по-прежнему сохраняется. Равенство в выражении (12.17) продолжает сохраняться и для всех ребер тех цветков, которые были срезаны, образовав псевдовершины графа Таким образом, если псевдовершина из была помечена как внешняя в альтернирующем дереве в старом графе то для некоторого ребра входящего в цветок, после срезания которого образовалась эта псевдовершина, веса уменьшатся на Но для множества вершин соответствующего этой псевдовершине, увеличится на так что равенство в выражении (12.17) по-прежнему сохранится для ребра Аналогично обстоит дело для ребер тех цветков, которые «порождают» псевдовершины в помеченные как внутренние вершины в дереве в старом графе

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

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

Наконец, если в то вычитание величины 2? из в процессе изменения вектора весов сделает в соответствии с (12.21) некоторое (скажем, равным нулю. Пусть

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 3. Если в не существует никакого альтернирующего дерева то строить новое дерево с корнем в некоторой

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

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

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

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

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

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

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

Шаг 6. Вычислить по формулам (12.19) — (12.22). Если нет никаких ограничений (12.19) — (12.21), то остановиться; в графе нет совершенного паросочетания. В противном случае изменить вектор весов как описано выше. Если или то сохранить текущее дерево и перейти к шагу 2. Если то перейти к шагу 7.

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

Конец

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