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

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

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

) Дерево строится отделено от графа и из графа не выбрасывается; если при построении дерева оно просто как-то выделялось (помечалось) в графе, то выбрасывание состоит в устранении всяких пометок, приписанных элементам дерева в этом процессе.- Прим. ред.

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

(I) дерево станет аугментальным, или

(II) на дереве появится цветок, или

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

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

В случае (II) обнаруживается получившийся цветок (как описано в разд. 2.2), срезается и продолжается рост дерева в процессе поиска аугментальной цепи. Что касается вычислительной стороны, то срезание не производится явным образом . Достаточно пометить все вершины цветка как внешние и отметить, что все они принадлежат этому цветку. Порядок, в котором цветки срезаются , важен, так как в конце всей процедуры цветки должны расцвести в обратном порядке.

В случае (III) вершины венгерского дерева и инцидентные им ребра совсем удаляются из графа (в соответствии с теоремой 4) и алгоритм применяется к оставшемуся подграфу.

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

Начальная установка.

Шаг 1. Выбрать в G начальное паросочетание М. Выбор корня.

Шаг 2. Если в G существуют по крайней мере две экспонированные вершины, то взять одну из них в качестве корня; в противном случае перейти к шагу 8.

Шаг 3. Взять внешнюю вершину Хо дерева. Для каждого ребра {хо, Xi): если Xi - экспонированная вершина, то перейти к шагу 4; если Xi - внутренняя вершина, то перейти к шагу 7; если Xi не принадлежит дереву и не является экспонированной, то перейти к шагу 5.



Шаг 4. Найдена аугментальная цепь из корня к х,. Построить новое улучшенное паросочетание, удаляя текущее дерево и пометки вершин, и перейти к шагу 2.

Шаг 5. Добавить к альтернирующему дереву ребро (Хо, и отметить вершину Xi как внутреннюю. Найти ребро {Xi, х^), принадлежащее текущему паросочетанию, и добавить его к дереву, пометив вершину х^ как внешнюю. Если существует ребро между Xii и другой внешней вершиной, то перейти к шагу 6. В противном: случае перейти к шагу 3.

Шаг 6. Опознать и срезать получившийся цветок. Отметить возникшую псевдовершину как внешнюю. Внести поправку в частичное упорядочение цветков и возвратиться к шагу 3.

IJfaг 7. Возвращаться к шагу 3 до тех пор, пока единственным возникающим случаем не будет случай (П1). Тогда удалить все вершины дерева и все ребра из G, инцидентные этим вершинам. Считать оставшийся подграф графом G и вернуться к шагу 2

Шаг S. Выделить отдельно в последнем графе Сив каждом удаленном венгерском графе оптимальное паросочетание, поступая так. Распустить сначала крайний цветок и выделить паросочетание, которое оставляет экспонированной относительно него ту вершину X, которая входит в паросочетание в нераспустившемся цветке. (См. теорему 2.) Продолжать процесс распускания в порядке, обратном к установленному на шаге 6, до тех пор, пока весь граф не будет распустившимся и не будет получено наибольшее паросочетание.

2.5. Пример

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

На шаге 2 алгоритма в качестве корня выбирается вершина Ху, и после нескольких применений шагов 3 и 5 получается альтернирующее дерево, изображенное на рис. 12.116. На этой стадии сразу же после добавления ребер {xg, Xg) и {xg, Хд) к альтернирующему дереву шаг 6 опознает цветок (xg, Xg, Хд, х^, х^), дающий после срезания псевдовершину by, и приводит к дереву, изображенному на рис. 12.Ив.

Следующее применение шага 3 добавляет ребра {by, аг) (на самом деле (4, Ху)) и {хуо, Хуу), как показано на рис. 12.11 г. Второй цветок {by, Хуо, Хуу, х„ Xg) опознается на шаге 6. После




26 25 18

Рис. 12.11а. Граф из примера 2.5. - Ребра в паросочетании.


Рис. 12.116. Альтернирующее дерево в графе из рис. 12.11а.

112 13

Ф

Корень

Рис. 12.Ив. Дерево после срезания цветка bj.



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