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

Чтобы построить остовный лес, начнем с узла Vi. ПОИСК (wi) вызывает ПОИСК (Уа), а тот вызывает ПОИСК (уз). Последний вызов ничего не добавляет к дереву, ибо единственное ребро с началом Vs идет в узел Vi, уже помеченный как "старый". Поэтому возвращаемся к ПОИСК (Уа), который добавляет Vt в качестве второго сына узла Уа- ПОИСК (У4) заканчивает работу, ничего не добавляя к лесу, поскольку узел Vs уже "старый". Затем заканчивается ПОИСК (Уа). ибо все ребра, выходящие из Уа, к данному моменту просмотрены. Поэтому возвращаемся обратно в Vi и вызываем ПОИСК (Уа)- Последний вызов ничего не добавляет к дереву; аналогично ничего не может добавить и ПОИСК (yj.

Теперь возьмем Уб в качестве корня нового глубинного остовного дерева. Его построение аналогично предыдущему, и мы оставляем его читателю. Заметим, что узлы посещались в порядке Vl, Уа, . . ., Vg. Следовательно, в процессе поиска в глубину узлу vt был приписан номер i, li8. □

При поиске в глубину на ориентированном графе в дополнение к древесным ребрам возникает еще три типа ребер. Это обратные ребра, такие, как (Уз, Vi) на рис. 5.13,6, поперечные справа налево, такие, как (У4, Уз) на том же рисунке, и прямые ребра, такие, как (Уь У4). Однако никакое ребро не идет из узла с меньшим номером, присвоенным в процессе поиска в глубину, в ребро с большим номером, если только последнее не является потомком первого. Это не случайно.

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

Поиск в глубину в графе G разбивает множество его ребер на четыре класса.

1) Древесные ребра, идущие к новым узлам в процессе поиска.

2) Прямые ребра, идущие от предков к подлинным потомкам, но не являющиеся древесными ребрами.

3) Обратные ребра, идущие от потомков к предкам (возможно, из узла в себя).

4) Поперечные ребра, соединяющие узлы, которые не являются ни предками, ни потомками друг друга.

Ключевое свойство поперечных ребер устанавливается в следующей лемме.



Лемма 5.6. Если (и, w) - поперечное ребро, то v-w, т. е. поперечные ребра идут справа налево.

Доказательств о. Доказательство аналогично доказательству леммы 5.3 и остается в качестве упражнения. □

5.5. СИЛЬНАЯ СВЯЗНОСТЬ

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

Определение. Пусть G= (V, Е) - ориентированный граф. Разобьем множество его вершин V на такие классы эквивалентности Vh что узлы V и W эквивалентны тогда и только тогда,

когда на графе есть пути из у в ш и обратно. Пусть Е,, -

множество ребер, соединяющих пары узлов в Vi. Графы Gi=(Vi, Ei) называются сильно связными компонентами графа G. Хотя каждый узел графа G принадлежит некоторому множеству Уг, у графа G могут быть ребра, не принадлежащие ни одному множеству Граф называется сильно связным, если он имеет только одну сильно связную компоненту.

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

Лемма 5.7. Пусть Gi= (Vi, Ei) - сильно связная компонента, ориентированного графа G, а S= (У, Т) - глубинный остовный лес для G. Тогда узлы графа Gi вместе с ребрами, входящими в пересечение Ei П 7", образуют дерево.

Доказательство. Пусть у и ау - узлы из Vi. (Мы предполагаем, что именами узлов являются номера, присвоенные им в процессе поиска в глубину.) Без потери общности будем считать, что у<ш. Так как узлы у и ш оба принадлежат одной и той же сильно связной компоненте, то существует путь Р в Gi, идущий из V в W. Пусть X - узел на Я с наименьшим номером (возможно, это сам узел у). Путь Р, дойдя до какого-нибудь потомка узла х, уже не сможет выйти за пределы поддерева потомков узла х, ибо за пределы этого поддерева выходят лишь поперечные ребра и обратные ребра, идущие в узлы с номерами, меньшими х. (Так



как потомки узла х занумерованы последовательно, начиная с х, то поперечное или обратное ребро, выходящее из поддерева потомков узла X, должно идти в узел с номером, меньшим х.) Следовательно, W - потомок узла х. Поскольку узлы занумерованы в прямом порядке, то все узлы, номера которых заключены между хяш, также являются потомками узла х. Так как а;у<ш, то у - потомок узла X.

Мы только что показали, что любые два узла в G; имеют общего предка в G;. Пусть т - общий предок узлов графа G, с наименьшим номером. Если v - узел графа Gu то любой узел на пути из r в у, проходящем в остовном дереве, также является узлом графа G,. □

Сильно связные компоненты ориентированного графа G можно найти, построив корни компонент в том порядке, в каком они встретились в последний раз в процессе поиска в глубину на G. Пусть Ti, Га, . . ., - эти корни В ТОМ порядке, в каком заканчивался их поиск в глубину (т. е. поиск узла заканчивался перед поиском /"j+i). Тогда для каждого /</ либо лежит слева от Tj, либо fi - потомок узла tj в глубинном остовном лесу.

Пусть Gj - сильно связная компонента с корнем Tj, lt. Тогда Gi состоит из всех потомков узла г, поскольку никакой узел Г), />1, не может быть потомком узла Гх. Аналогично можно доказать следующую лемму.

Лемма 5.8. Для любого i, \ik, граф Gi состоит из узлов, являющихся потомками узла ri и не принадлежащих ни одному из графов Gi, Ga, . . ., Gj i.

Доказательство. Корень Г} для />1 не может быть потомком узла /-j, поскольку вызов процедуры ПОИСК (о) завершается после работы процедуры ПОИСК (/"j). □

Для нахождения корней введем функцию, называемую НИЖ-НЯЯСВЯЗЬ:

НИЖНЯЯСВЯЗЬ [и] = МШ {{v} и {w I есть поперечное или

обратное ребро из некоторого потомка узла у в узел w, а корень той сильно связной компоненты, которая содержит W, является предком узла у}). (5.3)

На рис. 5.14 изображено поперечное ребро из потомка узла у в узел W, а корень г сильно связной компоненты, содержащей w, является предком узла у.

Мы скоро увидим, как в процессе поиска в глубину вычислять функцию НИЖНЯЯСВЯЗЬ. Но прежде охарактеризуем корни сильно связных компонент в терминах значений этой функции.





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