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

на различных узлах, или пройдя дерево на рис. 5.7,6 в прямом порядке. □

Особо отметим, что если v - подлинный предок узла w, то v<.w. Аналогично если v находится слева от ш в дереве, то v<Zw.

5.3. ДВУСВЯЗНОСТЬ

Рассмотрим приложение метода поиска в глубину к выделению в неориентированном графе двусвязных компонент. Пусть G= = {V, Е) - связный неориентированный граф. Узел а называют точкой сочленения графа G, если существуют такие узлы v и w, что V, W я а различны и всякий путь между v и w содержит узел а. Иначе говоря, а - точка сочленения графа G, если удаление узла а расщепляет G не менее чем на две части. Граф G называется дву-связным, если для любой тройки различных узлов и, w, а существует путь между V я W, не содержащий а. Таким образом, неориентированный связный граф двусвязен тогда и только тогда, когда в нем нет точек сочленения.

На множестве ребер графа G можно задать естественное отношение, полагая, что для ребер е, и выполняется это отношение, если 61=62 или они лежат на некотором цикле. Легко показать, что это отношение является отношением эквивалентности разбивающим множество ребер графа G на такие классы эквивалентности El, Е2, . . ., fft, что два различных ребра принадлежат одному и тому же классу тогда и только тогда, когда они лежат на общем цикле. Для ltfe обозначим через Vi множество узлов, лежащих на ребрах из Ej. Каждый граф Gi=(Vi, Ei) называется двусвязной компонентой графа G.

Пример 5.4. Рассмотрим неориентированный граф на рис. 5.8,а. Узел У4 является точкой сочленения, так как каждый путь между у, и у, проходит через У4. Классы эквивалентности, состоящие из ребер, лежащих на общих циклах, таковы:

{{Vi, Vi), (Vi, (Уз), (Уа, Уз)}, {К. 4)> (2. V,), (У4, V,)},

{К, .)}.

{(у.в, у,), (Ув, Ув), (Ув, Ув), (у„ Ув), (у,, у»)}.

Эти классы порождают двусвязные компоненты, изображенные на рис. 5.8,6. Не очевидно здесь лишь то, что ребро (у*, Уе), будучи

) R называется отношением эквивалентности на множестве S, если R рефлексивно {aRa для всех а S), симметрично (из aRb следует bRa для всех a,bS) и транзитивно (из aRb и bRc следует aRc). Легко показать, что отношение эквивалентности на S разбивает S на непересекающиеся классы эквивалентности. (Подмножество la]={b\bRa} называется классом эквивалентности.)




Рис. 5.8. а - неориентированный граф, 6 -• его двусвязные компоненты.

само классом эквивалентности (оно не входит ни в один цикл), порождает "двусвязную компоненту", состоящую из У4 и Ue. □

Следующая лемма дает полезную информацию о двусвязности.

Лемма 5.4. Пусть Gi={Vi, Ei) для lik - двусвязные компоненты связного неориентированного графа G= (У, Е). Тогда

1) граф Gi двусвязен для каждого i, \ik;

2) для всех 1Ф1 пересечение Vi П V} содержит не более одного узла;

3) а - точка сочленения графа G тогда и только тогда., когда aVif\V} для некоторых ij.

Доказательство. 1) Допустим, что найдутся такие три различных узла v, w я а в V,, что все пути в Gj между v » w проходят через а. Тогда, разумеется, (v, w)Ei. Следовательно, в Ei есть различные ребра (v, v) и (w, w), а в Gi - цикл, содержащий их. По определению дву связной компоненты все ребра и узлы на этом цикле принадлежат Ei и Vi соответственно. Поэтому в Gj есть два пути между v я w н только один из них содержит а; получили противоречие.

2) Допустим, что пересечению Vt Л Vj принадлежат два различных узла V я W. Тогда существуют цикл Ci в G/, содержащий v я w, и цикл Са в Gj, также содержащий ияш. Поскольку Et и Ej не пересекаются, то множества ребер, входящих в Ci и Са, тоже не пере-



секаются. Тем не менее из ребер этих циклов можно построить новый цикл, содержащий узлы v и w. Отсюда следует, что хотя бы одно ребро в Ei совпадает с каким-то ребром bEj. Таким образом, вопреки предположению Ei н Ej не являются классами эквивалентности.

3) Пусть а - точка сочленения графа G. Тогда существуют такие два узла v а w, что v, w и а различны и каждый путь между v и w содержит а. Так как граф О связен, то хотя бы один такой путь найдется. Пусть (х, а) и (у, а) - два ребра, лежащие на некотором пути между и и ш и инцидентные а. Если существует цикл, содержащий эти два ребра, то некоторый путь между v и w не содержит а. Следовательно, (х, а) и (у, а) входят в разные двусвязные компоненты, а узел а принадлежит пересечению множеств их узлов.

Обратно, если aVif] V], то найдутся ребра (х, а) и (у, а) соответственно в Ei н Е). Так как они не лежат оба на одном и том же цикле, то всякий путь из а; в г/ содержит а. Следовательно, а - точка сочленения. □

Поиск в глубину особенно полезен для нахождения двусвязных компонент неориентированного графа. Отчасти это связано с тем, что, согласно лемме 5.3, в нем нет "поперечных ребер". Иными словами, если узел v - не предок и не потомок узла w в остовном лесу, то у и йу не могут соединяться никаким ребром.

Если а - точка сочленения, то удаление ребра а и всех ребер, инцидентных ему, расщепляет граф G по крайней мере на две части.


Рис. 5.9. Остовное дерево, построенное поиском в глубину.





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