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

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

Ориентированный граф G= (V, Е) называется корневьш для (относительно) узла г, если существуют пути из г в каждый его узел. В остальной части раздела мы будем предполагать, что G= = (V, Е) - корневой ориентированный ациклический граф с корнем г.

Узел V называется доминатором узла ш, если любой путь из корня в W проходит через v. Каждый узел доминирует над самим собой, а корень доминирует над каждым узлом. Множество доми-наторов узла w можно линейно упорядочить, расположив их в порядке вхождения в какой-нибудь кратчайший путь из корня в w. Доминатор узла w, ближайший к нему и отличный от него, называется его непосредственным доминатором. Так как множество доминаторов каждого узла линейно упорядочено, то отношение доминирования можно представить деревом с корнем г, называемым доминаторным деревом для G. Вычисление доминаторов полезно в задаче оптимизации кодов (Ахо, Ульман [1973], Хект [1973]).

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

Пусть G=(V, £) - граф и G={V, £") - его подграф. Если (а, Ь)£Е, будем писать а вЬ. Через r-J, и будем обозначать соответственно транзитивное и рефлексивно-транзитивное замыкания отношения =>о/. Если (а, Ь)Е, будем писать а Ь.

Лемма 5.12. Пусть G={V, Е) - ориентированный ациклический граф с корнем г, а S= (V, Т) - остовное дерево для него с корнем г, построенное поиском в глубину. Пусть а, Ь, с и d - такие узлы из V, что а =>s =>J с =>s d. Далее, пусть (а, с) и (Ь, d) ~ прямые ребра. Тогда замена прямого ребра (Ь, d) прямым ребром (а, d) не меняет доминаторов никакого узла в G (см. рис. 5.28).

Доказательство. Обозначим через G граф, полученный при замене ребра (Ь, d) в G ребром (а, d). Допустим, что v - доминатор узла w в G, но не в G. Тогда в G найдется путь Р из г в W, не содержащий v. Очевидно, что этот путь должен идти по ребру (а, d), поскольку это единственное ребро в G, которого нет в G. Поэтому можно написать Р: г =$>* а d =>* ш. Отсюда следует, что узел V должен лежать на пути а =>5 d и что он отличен от а и d. Если а<РЬ при нумерации, порождаемой поиском в глубину, то замена ребра а d в Р на путь а с => d дает путь в графе G,





Рис. 5.28. Преобразование из леммы 5.12.

идущий ИЗ Г В ш И не содержащий и. Если b<.v<.d, то замена ребра а => d в Р на путь а =>s Ь => d дает путь в графе G, идущий из г в ш и не содержащий v. Так как a<vb или Ь<х)<.й, то найдется путь в G, идущий из г в О) и не содержащий v; получили противоречие.

Допустим, что V - доминатор узла w в G, но не в G. Тогда в G найдется путь Р из г в ау, не содержащий v. Так как этот путь не проходит целиком в G, то он должен содержать ребро b d. Следовательно, узел V лежит на пути b =>* d и b<.v<Cd. Таким образом, в G есть путь г =>s а => d у, не содержащий узел у; получили противоречие. □

Лемма 5.13, Пусть G и S те же, что и в лемж 5.12, а =>s Ь и (а, Ь) - прямое ребро графа G. Если в G нет прямого ребра (c,d), для которого с<.а и a<d<fc, и поперечного ребра (е, d), для которого a<d6, то удаление древесного ребра, входящего в Ь, не меняет доминаторов никакого узла в G (см. рис. 5.29).

\ Нет прямых аЛ \ребер этого

Нет входящих поперечных <>



Рис. 5.29. Преобразование из леммы 5.13.





. Нет входящих поперечных ребер

Рис. 5.30. Преобразование из леммы 5.14.

Доказательство. Доказательство аналогично доказательству леммы 5.12. □

Лемма 5.14. Пусть G и S те же, что и в лемме 5.12, (с, d) - поперечное ребро графа G и b - общий предок для с и d с наибольшим номером. Пусть a=«MIN ({&} и {и (и, w) - прямое ребро и Ь<.хюс}). Если ни в один узел пути b => с, отличный от Ь, не входит поперечное ребро, то замена поперечного ребра (с, d) прямым ребром (а, d) не меняет доминаторов никакого узла в G (см. рис. 5.30).

Доказательство. Обозначим через G граф, полученный при замене ребра (с, d) в G ребром (а, d). Допустим, что v - доминатор узла w в G, но не в С. Тогда в G найдется путь Р из г в 14), не содержащий и. Понятно, что этот путь должен идти по ребру (а, d). Следовательно, узел v должен лежать на пути а проходящем по остовному дереву, ибо в противном случае замена ребра a=dB Р Haa=>ld или на а =5 с = d дала бы путь в G, идущий из г в 14) и не содержащий v. Но тогда замена ребра а d в Р на а = ы =>s с d, где и лежит на пути й с и ы>&, дала бы путь в G, идущий из г в ш и не содержащий и; получили противоречие.

Допустим, что V - доминатор узла w в G, но не в G. Тогда в G найдется путь Р из г в w, т содержащий о. Понятно, что Р содержит ребро (с, d). Запишем Р в виде г с = d = s t4). Путь г =>J с должен содержать узел, лежащий на пути а b, поскольку нет поперечных ребер, входящих в узлы на пути &=s с (исключая узел Ь). Пусть х - такой узел с наибольшим номером, а Pi - участок пути Р от г дох, за которым следует а за ним

участок пути Р от d до w. Пусть Pt - путь г =s a=d, за которым





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