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

Одна из них состоит из сына s узла а и всех его потомков в глубинном остовном дереве. Следовательно, в этом остовном дереве узел а должен иметь сына s, потомки которого не соединены обратными ребрами с подлинными предками узла а. Обратно, из-за отсутствия поперечных ребер узел а, отличный от корня, является точкой сочленения, если никакой потомок некоторого его сына не соединен обратным ребром ни с каким подлинным предком узла а. Корень глубинного остовного дерева является точкой сочленения тогда и только тогда, когда он имеет не менее двух сыновей.

Пример 5.5. Остовное дерево, построенное поиском в глубину, для графа, изображенного на рис. 5.8,а, показано на рис. 5.9. Точками сочленения являются v, V4 и v. Узел имеет сына v, и ни из какого потомка узла Vi не выходит обратного ребра к подлинному предку узла v. Аналогично узел имеет сына Ув, а Уб - сына Dj с подобными свойствами. □

Высказанные выше идеи выражены в следующей лемме.

Лемма 5.5. Пусть G- {V, Е) - связный неориентированный граф, а S=(V, Т) - глубинное остовное дерево для него. Узел а является точкой сочленения графа G тогда и только тогда, когда выполнено одно из условий:

\) а - корень и а имеет более одного сына;

2) а - не корень и для некоторого его сына s нет обратных ребер между потомками узла s (в том числе самим s) и подлинными предками узла а.

Доказательство. Легко показать, что корень является точкой сочленения тогда и только тогда, когда у него больше одного сына. Эту часть оставляем в качестве упражнения.

Предположим, что условие 2 выполнено. Пусть / - отец узла а. По лемме 5.3 каждое обратное ребро идет из некоторого узла в его же предка. Следовательно, любое обратное ребро, выходящее из потомка V узла s, идет к предку узла v. По условию леммы обратное ребро не может идти к подлинному предку узла а. Поэтому оно идет либо к а, либо к потомку узла s. Таким образом, всякий путь из S в / содержит а, откуда вытекает, что а - точка сочленения.

Для доказательства обратного утверждения допустим, что а - точка сочленения, отличная от корня. Пусть х я у - различные узлы, отличные от а и такие, что всякий путь в G между а; и г/ содержит а. По крайней мере один из узлов х я у, скажем х, является подлинным потомком узла а в S; в противном случае в G был бы путь между X я у, проходящий по ребрам из Г и не содержащий а. Пусть S - такой сын узла а, что х - потомок узла s (возможно, x=s). Тогда либо между потомком v узла s и подлинным предком w узла а нет обратного ребра и, значит, условие 2 выполняется, либо





Рис. 5.10. Пути для контрпримеров.

такое ребро (и, w) есть. В этой ситуации надо рассмотреть отдельно два случая.

Случай 1. Допустим, что у - не потомок узла а. Тогда из х в у и далее ъ w н у идет путь, не содержащий а; получили противоречие (см. рис. 5.10,а).

Случай 2. Допустим, что у - потомок узла а. Ясно, что у - не потомок узла s, ибо иначе был бы путь из а; в г/, не содержащий а. Пусть s - такой сын узла а, что у - потомок узла s. Тогда либо между потомком v узла s и подлинным предком w узла а нет обратного ребра и, значит, условие 2 выполняется, либо такое ребро (и, w) есть. В последнем случае из х в у и далее bw, v и у идет путь, не содержащий а; получили противоречие (см. рис. 5.10,6). Итак, условие 2 выполнено. □

Пусть Т я В - множества соответственно древесных и обратных ребер, построенных поиском в глубину в связном неориентированном графе G= (V, Е). Мы будем считать, что узлам в V приписаны их номера в последовательности, образованной в процессе поиска в глубину. Для каждого у из У определим

НИЖНИЙ [у] =МШ ({у} и {w I существует такое обратное ребро {х, w)B, что а;-потомок узла у, а w-предок узла у в глубинном остовном лесу (V, Т)}). (5.1)



Нумерация в прямом порядке обладает тем свойством, что если X - потомок узла v, а {х, ш) - обратное ребро, причем w<.v, то W - подлинный предок узла v. Следовательно, по лемме 5.5, если V-не корень, то v является точкой сочленения тогда и только тогда, когда имеет сына s, для которого НИЖНИЙ[5]у.

В процедуру ПОИСК можно включить и вычисление значения функции НИЖНИЙ для каждого узла, если переписать (5.1) так, чтобы выразить НИЖНИЙ[у] через узлы, смежные с у, используя обратные ребра и значения НИЖНИЙ на сыновьях узла v. Точнее, НИЖНИЙ[у] можно вычислить, определив наименьшее значение тех узлов W, которые обладают хотя бы одним из свойств

1) w=v,

2) йУ=НИЖНИЙ[5] и S - сын узла у,

3) (у, w) - обратное ребро в В.

Наименьшее значение w можно будет определить, как только будет исчерпан список L[v\ узлов, смежных с у. Таким образом, (5.1) эквивалентно равенству

НИЖНИЙ [у] =МШ({у и {НИЖНИЙ [s] s сын узла у} и

[]{w\(v,w)B\). (5.2)

В новый вариант процедуры ПОИСК, приведенный на рис. 5.11, мы включили как переименование узлов по первому посещению, так и вычисление функции НИЖНИЙ. В строке 4 величине НИЖ-НИЙ[у] придается начальное значение, равное ее максимально возможному значению. Если у имеет сына w в глубинном остовном лесу, то в строке 11 корректируется значение НИЖНИЙ[у], если оно оказывается больше, чем НИЖНИЙ[гг;]. Если узел у соединен обратным ребром с узлом w, то в строке 13 полагаем НИЖНИЙ[у1= = irHOMEPliw] при условии, что номер узла w в поиске в глубину меньше текущего значения НИЖНИЙ[у]. Текст в строке 12 проверяет, не является ли ребро (у, w) обратным из-за того, что w - отец узла V в глубинном остовном дереве. Таким образом, рис. 5.11 реализует формулу (5 2).

Вычислив значение НИЖНИЙ[у] для каждого узла у, легко найти точки сочленения. Сначала изложим полный алгоритм, а затем докажем его корректность и покажем, что он требует время О {г).

Алгоритм 5.3. Нахождение двусвязных компонент

Вход. Связный неориентированный граф G= (У, Е). Выход. Список ребер каждой двусвязной компоненты графа G. Метод.

1. Вначале полагаем Т=0 и СЧЕТ=1. Помечаем каждый узел в V как "новый", выбираем произвольный узел Уо в V и вызы-





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