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

следует участок пути Р от d до w. Если узел v лежит на Pi, то он должен лежать и на х zs d, причем v>x. Если он лежит на Ра, то должен лежать на г zs - Так как ах, то один из этих путей в G не содержит v; получили противоречие. □

Легко показать, что повторное применение преобразований из лемм 5.12-5.14 до тех пор, пока возможно, переводит граф G в дерево. Так как эти преобразования не меняют отношения доминирования, то окончательное дерево должно быть доминаторным для G. Это и будет нашим алгоритмом вычисления доминаторов графа G. Вся хитрость - в построении структуры данных, позволяющей эффективно находить подходящие ребра, к которым надо применять преобразования из лемм 5.12-5.14.

Говоря неформально, можно сказать, что мы строим доминатор-ное дерево для данного ориентированного ациклического графа G= {V, Е) следующим образом. Сначала поиском в глубину строим в G, отправляясь от корня, соответствующее остовное дерево S= = (V, Т). Номера узлов графа G меняем на их номера, порожденные поиском в глубину. Затем применяем к G преобразования из лемм 5.12-5.14. Они выполняются двумя взаимосвязанными подпрограммами, одна из которых обрабатывает прямые ребра, а другая - поперечные.

/. Прямые ребра

Предположим на время, что в G нет поперечных ребер. Если в узел V входит более одного прямого ребра, то по лемме 5.12 все прямые ребра, входящие в v, за исключением одного с наименьшим началом, можно удалить, не изменив доминаторов ни одного узла.

Составным ребром назовем упорядоченную пару (t, Н), где t - узел, называемый началом составного ребра, а Я - множество узлов, называемое концом составного ребра. Составное ребро {t, {hi, Ла, . . ., /tfc}) представляет множество ребер (t, hi), {t, ha), . . .

..., {t. К).

Многократно применяем лемму 5.12, чтобы изменить начала прямых ребер. В какой-то момент начало каждого ребра из множества ребер с общим началом t изменится на t. Чтобы сделать это эффективно, представим одним составным ребром некоторые множества прямых ребер с общим началом. Вначале каждое прямое ребро (t. К) представляется составным ребром (t, {h)).

Каждому узлу v графа G поставим в соответствие множество F[v]. Это множество содержит такие пары {t, {hi, ha, . . ., h}), что t - предок узла v, каждый узел hi - потомок узла v и {t, hi) - прямое ребро в G. Вначале F[v]={{t, {v})}, где - начало (с наименьшим номером) прямого ребра с концом и.

Затем проходим остовное дерево в порядке, обратном к прямому. Возвращаясь по ребру (и, w) остовного дерева, обнаруживаем,




Рис. 5.31. Корневой ориентированный ациклический граф.

что множество F[w] содержит составное ребро для каждого подлинного предка t узла w, который в данный момент является началом прямого ребра для некоторого потомка узла гю. Далее делаем следующее.

1) Пусть (t, {hi, hi, . . ., h„)) - составное ребро в F[w], имеющее начало с наибольшим номером. Если t=v, удаляем его из F[w]. (Это составное ребро представляет множество прямых ребер, начала которых перемещены в узел v, но больше не будут перемещаться под действием преобразования из леммы 5.12.) Удалим из G ребро остовного дерева с концом hi, 1<1</п.

2) Если есть в G прямое ребро [t, v) то для каждого составного ребра {и, {hi, . . ., h„)) из Fiw], для которого ut,

(а) удаляем (н, {hi, . . ., h„}) из Flw],

(б) объединяем {hi, . . ., h„} с концом того составного ребра из F[v], которое представляет среди прочих и ребро (t, v).

3) Заменяем F[v] на Flv] и F[w].

(Шаг 1 соответствует применению леммы 5.13, а шаг 2 - леммы 5.12.)

Пример 5.15. Рассмотрим корневой ориентированный ациклический граф G, изображенный на рис. 5.31. Поиск в глубину на графе G может породить граф, изображенный на рис. 5.32,а, где указаны также f-множества, поставленные в соответствие каждому узлу. На рис. 5.32,6 - г приведены результаты преобразований прямых ребер. Окончательное доминаторное дерево изображено на рис. 5.32,г. □

Оставляем читателю доказать, что по достижении корня действительно получается доминаторное дерево (в предположении, что

1) Напомним, что мы предполагаем, что все прямые ребра с концом v, кроме имеющих начало с наименьшим номером, удалены из С



/[1] = 0 Г[2] = 0


\-[б] = {(2,{6})} /

* [4]-{(1,<4»>/

[7] = {(3,<7»}

[ll=0 Ш-0


\ ум={(1.-!3))>

W6]={(2.-(6,7})}


[3]={(1Д3.4,5,6.7})}


Рис. 5.32. Результаты преобразований прямых ребер; а - вначале; б - по возвращении вдоль ребра (6, 7) остовного дерева; в - по возвращении вдоль ребра (3, 4) остовного дерева; г - по возвращении вдоль ребра (1, 2) остовного дерева.

нет поперечных ребер). Этот алгоритм можно эффективно реализовать с помощью алгоритма объединения непересекающихся множеств и обрабатывать им множества концов у составных ребер. Множества F[v\ составных ребер можно представить 2-3-деревьями. Это связано с тем, что мы должны уметь эффективно удалять составные ребра, выделять в множестве составных ребер ребро с наибольшим началом и строить объединение множеств составных ребер. При такой структуре данных для обработки графа с е ребрами требуется время О (е log е).

2. Поперечные ребра

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





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.0038