Главная Промышленная автоматика.

) См. примечание на стр. 202, -Прим. ред.

торая строится в п. 1, помогает эффективно применить лемму 5.14. С другой стороны, не надо полностью выполнять п. 1 до устранения поперечных ребер, поскольку каждое устраненное поперечное ребро становится прямым. На самом деле мы должны добавить шаги обработки поперечных ребер к тому прохождению в порядке, обратном к прямому, которое было описано применительно к прямым ребрам. Заметим, что в п. 1 требуется (из-за применения леммы 5.13), чтобы в определенные моменты времени в определенные узлы не входили поперечные ребра. Поскольку прохождение ведется в порядке, обратном к прямому, шаги, описанные ниже, преобразуют поперечное ребро в прямое перед тем моментом, когда его наличие делало лемму 5.13 неприменимой.

Пусть S - глубинное остовное дерево для G. Вначале для каждого поперечного ребра (о, w) вычисляем общего предка узлов v и W с наибольшим номером. Каждому узлу v припишем множество Llv] упорядоченных пар (и, w), где (и, w), u>w, представляет запрос о предке узлов ы и te» с наибольшим номером. Вначале L\v\= = {(о, w)\ есть поперечное ребро (о, w), V>w). Во время прохождения дерева S в соответствии с процедурой в п. 1 делаем следующее.

1) При прохождении древесного ребра (у, w), v<.w, удаляем из L[v каждую пару (х, у), в которой ухю. Узел у - общий предок с наибольшим номером узлов х vi у.

2) По возвращении к у по ребру (о, w) остовного дерева заменяем L{v\ на L[v\\jL{w\.

Вычисление предков с наибольшим номером можно осуществить не более чем за 0(еО(е)) шагов*), где в - число ребер графа G; для этого можно воспользоваться обобщением MIN-алгоритма, работающим в свободном режиме, о котором упоминается в упр. 4.21.

Обработка поперечных ребер состоит в том, что они преобразуются в прямые по лемме 5.14. Процесс преобразования поперечных ребер в прямые надо выполнять во время обработки прямых ребер. Каждому узлу у ставим в соответствие некоторое множество С[у] составных ребер. Вначале С[у]={(у, %...../г„})(у, /i;) - поперечное ребро при Xt/n}. По возвращении в узел у вдоль древесного ребра (у, w) совершаем помимо шагов, связанных с обработкой прямых ребер, следующие шаги.

1) Заменяем С[у] на СЫиСЫ.

2) Удаляем каждое поперечное ребро {х, у), для которого у - предок с наибольшим номером узлов х vi у, т составного ребра, где оно представлено в данный момент. Если t - начало этого составного ребра, заменяем поперечное ребро {х, у)




Г\ С[6] = {(6,<5})> ( / I

C\b]-{(S,W)}

£[11-0


Рис. 5.33. Удаление поперечных ребер: а - вначале; б - после рассмотрения

ребра (3, в).

прямым ребром {t, у). Если в у уже входит прямое ребро, оставляем только прямое ребро с тем началом, у которого номер меньше.

3) Пусть (ы, и) - прямое ребро (если оно есть) с концом и. Если такого ребра нет, то пусть (н, v) - древесное ребро, входящее в v. После просмотра всех потомков узла v удаляем из C[v] все составные ребра, начала которых лежат выше и. Объединяем множества концов удаленных составных ребер и образуем новое составное ребро с началом и. Добавляем новое составное ребро к Civ].

Пример 5.16. Рассмотрим глубинное остовное дерево на рис. 5.33,а. Значения Civ] приведены для обрабатываемых узлов. Так как из узла 2 в узел 8 идет прямое ребро, заменяем составное ребро (8, {4}) в С18] на (2, {4}). Затем присоединяем С[8] к С[7]. Так как (1, 7) - прямое ребро, преобразуем составное ребро (2, {4}) в (1, {4}). По возвращении в узел 6 множество С[6] станет равным {(1, {4}), (6, {5})}.

По возвращении из узла 6 в узел 3 множество С[3] становится равным {(3, {5}), (1, {4})}. Узел 3 является предком с наибольшим номером узлов 6 и 5 и узлов 8 и 4. Поэтому удаляем из С[3] состав ные ребра (3, {5}) и (1, {4}) и добавляем к G прямые ребра (3, 5) и (1, 4). Результат показан на рис. 5.33,6. Последующая часть поиска не приводит ни к каким изменениям. □

Составные поперечные ребра можно представить 2-3-деревьями. Предлагаем в качестве упражнения формальное описание домина-торного алгоритма. Если вы сможете найти подходящие структуры, вы освоили технику гл. 4 и 5.



УПРАЖНЕНИЯ

УПРАЖНЕНИЯ

5.1. Найдите остовное дерево наименьшей стоимости для графа на рис. 5.34, если все нарисованные ребра неориентированны.

5.2. Пусть S = (V, Т) - остовное дерево наименьшей стоимости, построенное алгоритмом 5.1. Пусть сСа. . .с„ - стоимости ребер в Т. Пусть S - произвольное остовное дерево со стоимостями ребер didi. . Покажите, что Ctdt для

**5.3. Чтобы за время 0(e) построить остовное дерево наименьшей стоимости для графа с п узлами и е ребрами в предположении, что ef{n), где / - некоторая функция, которую вы должны найти, можно воспользоваться следующей стратегией. В различные моменты времени узлы будут группироваться в множества, связанные древесными ребрами, которые к тому времени уже найдены. Все ребра, инцидентные одному или двум узлам из множества, будут храниться в приоритетной очереди для этого множества. Вначале каждый узел находится в множестве, состоящем из него самого.

Итерируемый шаг состоит в том, чтобы найти наименьшее множество S и ребро с наименьшей стоимостью среди всех ребер, выходящих из S; пусть это ребро ведет в множество Т. Затем добавляем его к остовному дереву и сливаем множества S и Г. Но если все множества имеют размер не меньше g{n), где g - другая функция, которую вам надо найти, то вместо этого образуем новый граф, где каждое множество представлено одним узлом. Узлы нового графа, соответствующие множествам Si и Sj, полагаются смежными, если некоторый узел в Si был смежен некоторому узлу в Sa в исходном графе. Стоимостью ребра, соединяющего Si и Sa в новом графе, считается наименьшая из стоимостей ребер, соединяющих узел из Si с узлом из Sa в исходном графе. Далее этот алгоритм рекурсивно применяется к новому графу.

Ваша задача - выбрать g (п) так, чтобы минимизировать / (п).


Рис. 5.34.





0 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 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002