Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 [ 125 ] 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141


состоит из единственного такого цикла, как показано на рис. 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, И].

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



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 [ 125 ] 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95