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

Предположим, что мы начинаем с графа G. Присвоим его вершинам веса я, выбирая величины я, достаточно большими, чтобы ограничения (12.17) выполнялись, когда все V взяты равными нулю. Пусть теперь G - остовный подграф в G, содержащий только те ребра, для которых в (12.17) имеет место равенство. Назовем G специальным остовным подграфом графа G. Если в G можно найти совершенное паросочетание (с помощью алгоритма для ЗНПС, описанного в предыдущем разделе), то это паросочетание - оптимальное. Действительно, вектор [я, Х^] удовлетворяет ограничениям (12.17) и (12.18), условие (i) выполнено автоматически, так как Х^ = О для всех г, а условие (ii) выполнено ввиду того, что в паросочетание входят только ребра из G, так что Ij не может быть Ф О, если Uj не удовлетворяет ограничению (12.17).

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

при условии

Яг + яь+ S K>Cj, V/ = l, .... m (12.17)

и

lr>0 для всех Sr. (12.18)

Таким образом, с каждой вершиной Xt из G связана некоторая переменная Я;, а с каждым множеством Sr, состоявшим из нечетного числа вершин, связана переменная Хг.

В ограничениях (12.17) cj - вес ребра а, вида {xt, х^), а Fj = = {Sr I aj 6 Аг}, т. е. Fj - семейство подмножеств S, содержавших как Xi, так и х^. В соответствии с теоремой двойственности линейного программирования вектор [f] максимизирует z при условиях (12.12), (12.14) и (12.15), а вектор [л*, Х^] минимизирует и при условиях (12.17) и (12.18) тогда и только тогда, когда

(i) для каждого к* или = О, или же в соответствующем ограничении (12.14) имеет место равенство;

(ii) для каждого * или * = О, или же в соответствующем ограничении (12.17) имеет место равенство.

Мы дадим доказательство теоремы 5, описав процедуру, позволяющую находить совершенное паросочетание М (и, следовательно, вектор [1]], а также вектор [я*, Х*], удовлетворяющий условиям (12.17) и (12.18) и условиям двойственности (i) и (ii)). Таким образом будет доказано, что М - оптимальное паросочетание.

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

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

Для более ясного понимания алгоритма мы введем следующую индексацию. Первоначальный граф G будет обозначаться через Gq. Специальный остовный подграф графа Gq есть GJ; в этом графе строится альтернирующее дерево, как это делалось в алгоритме для ЗНПС. Когда, наконец, образуется и срезается первый цветок, сам граф будет обозначаться через Gi, а его специальный остовный подграф - через G2. После срезания / цветков граф будет обозначен символом Gf, а его специальный остовный подграф - Gf+i.

Общий шаг алгоритма таков. Пусть очередной граф (после срезания некоторого числа цветков) будет G, j, а его специальный остовный подграф - G}. В Gf строится альтернирующее дерево - с помощью алгоритма ЗНПС - до тех пор, пока не произойдет одно из трех:

A) на дереве появится цветок; Б) дерево станет аугментальным;

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

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

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

Дерево Т следует отбросить ) и, взяв в графе G, оставшуюся экспонированную (в Gf) вершину, приступить к построению нового дерева с корнем в этой вершине. Здесь следует заметить, что как только Т отброшено и в начинает расти новое дерево , некоторые из псевдовершин в Щ (образованные после срезания более ранних цветков, давших графы Gq, Gi, . . ., G/ i) могут оказаться помеченными как внутренние в новом дереве.

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

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

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

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

Изменения в векторе весов [я;, Я^] производятся так. Для ребер aj = {xi, х^) из G/ i, не принадлежащих G/, одна концевая вершина которых принадлежит текущему альтернирующему дереву Г и помечена как внешняя, а другая концевая вершина не лежит в Т, находим

А1 = т1п[я;Ч-Яй-с^]. (12.19)

Для ребер aj == (Xj, хи) из Gf i, не принадлежащих Gf, обе концевые вершины которых лежат в Г и обе помечены как внешние, находим

А2 = утт[яг-ЬЯй-с^.]. (12.20)

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

Аз = 1 min [Я,]- (12.21)

Берем

A = min[Ai, Аг, Аз]. (12.22) ) См. примечание 2 на стр. 382.- Прим. ред.