состоит из единственного такого цикла, как показано на рис. 12.9, то решение задачи линейного программирования (12.2) и (12.3)

В последнем из двух упомянутых случаев вершина Xi может быть оставлена экспонированной, а остальные а - 1 вершин из В разобьются на пары, порождая паросочетание, как и выше. Цветок Bi - это цикл с нечетным числом ребер, и, следовательно, получается такая же самая ситуация относительно Bi, какая уже обсуждалась в случае цветка В, так что экспонированной в конце КОНЦОВ останется только вершина х.

Важность цветков и циклов (цепей) с нечетным числом ребер в задачах о паросочетаниях можно оценить, анализируя следующий факт: при отсутствии таких циклов формулировка ЗМП на языке линейного программирования, даваемая соотношениями (12.2) и (12.3), приводит к собственно целочисленному решению, так ЧТО ограничения (12.4) становятся излишними [8, 16, 17]. Графы, не содержащие циклов с нечетным числом ребер, являются двудольными графами; они рассматриваются в последующих параграфах. Общие свойства полиэдров, определяемых соотношениями (12.3), содержатся в следующей теореме Балински [1].

Теорема 3. Все вершины выпуклого полиэдра, задаваемого неравенствами

где [bij] - матрица инциденций графа, имеют координаты со значениями О, 1/2 или 1.

Случай нецелочисленных значений (а именно значения 1/2) отвечает циклам с нечетным числом ребер. Если, например, граф

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

-Ребра, лежащие в дереве, но не

принадлежащие паросочетанию ---Ребра, не лежащие в дереве

Рис. 12.10. Венгерское дерево.

показано венгерское дерево, причем жирными линиями изображены ребра, входящие в паросочетание, а светлыми - остальные. Ребра графа, не принадлежащие дереву, показаны пунктиром.

Важность венгерских деревьев для ЗМП объясняется следующим их свойством.

Теорема 4 [10]. Пусть П - венгерское дерево в графе G = = {X, А) и Go = {X - Хн) - порожденный подграф графа G, тсключающий из G множество вершин Хд дерева П. Если Mjj - паросочетание в дереве Л и Mqo - наибольшее паросочетание в Go, то множество ребер MUMgo является наибольшим паросочетанием в G.

ДЛЯ ЗНП таково: Zj = 1/2 для 7 = 1, . . ., 5. Значение этого решения будет 2-, в то время как очевидно, что наибольшее паросочетание для графа на рис. 12.9 содержит два ребра.

2.3. Венгерские деревья

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

Доказательство. Пусть множество А ребер графа G разбито на три подвтожества:

А„ = {{Xi, Xj) I {Xi, Xj) б Л И xt,xj£ Xfj},

AHG = {{Xi, Xj)\{Xi, Xj)A, XiXn И Xj£X - Xh},

AGo = {{Xi, Xj)\{Xi, Xj)A и Xi, XjX - Xh}.

Если S - произвольное паросочетание в G, то 5 может быть разбито аналогичным образом, так что

5 = Sh и Shgo и Sgo, где Sh = S{]Ah, SHG = Si]AnGg и SG = Si]AG. По определению паросочетания Мсо мы имеем

\М*Сд\\8со\. (12.8)

Рассмотрим теперь граф G, состоящий из ребер AIjAhgo и их концевых вершин. По отношению к Мн все вершины 6 X-

- Хн, являющиеся концевыми для ребер из АнОо, будут зкспони-рованными. Альтернирующая цепь, начинающаяся в зкспониро-ванной вершине х^ Е X - Хн (или начинающаяся в корне дерева Н, который также является экспонированной вершиной), может только тогда быть аугментальной, когда она оканчивается в другой вершине х^ X - Хц- Но аугментальная цепь должна содержать нечетное число ребер, а это означает, что если первое ребро этой цепи идет из экспонированной вершины во внутреннюю, то последнее ребро должно идти из внешней вершины в экспонированную. Так как по определению дерева Н все ребра в Анвп лежат между внутренними вершинами Н и вершинами из X -

- Xfi, то в графе G нет никакой аугментальной цепи и, следовательно, Мн является наибольшим паросочетанием в G, т. е.

\Ма\>\8н\ + \8нсо\. (12.9)

Из (12.8) и (12.9) получаем

\Мн[}МЬА>\Зн[} ShGo[iSGo\>\S\. (12.10)

Таким образом. Ми [} МЬа является наибольшим паросочетанием в G.

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

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

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