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

Метод. begin

СЧЕТ.-1;

for vV do пометить узел v как "новый"; сделать СТЕК пустым;

while существует узел v, помеченный как "новый" do ПОИСКЕ (V)

end □

Пример 5.8. Рассмотрим глубинный остовный лес на рис. 5.13. Этот лес воспроизведен на рис. 5.16, где указаны также значения функции НИЖНЯЯСВЯЗЬ. Вызов ПОИСКЕ (3) заканчивает работу первым среди всех вызовов процедуры ПОИСКЕ. Когда мы исследуем ребро (3,1), полагаем НИЖНЯЯСВЯЗЬ[3]=МШ(1, 3) = 1. По возвращении к ПОИСКЕ (2) полагаем НИЖНЯЯСВЯЗЬ [2]= =МШ(2, НИЖНЯЯСВЯЗЬ[3]) = 1. Затем вызываем ПОИСКЕ (4) для исследования ребра (4, 3). Так как 3<4 и 3 еще находится в СТЕКе, полагаем НИЖНЯЯСВЯЗЫ4]=МШ (3, 4)=3.

Затем возвращаемся к вызову ПОИСКЕ (2) и полагаем НИЖ-НЯЯСВЯЗЫ2] равным меньшему из чисел: НИЖНЯЯСВЯЗЬ[4] и текущего значения НИЖНЯЯСВЯЗЫ2] (равного 1). Поскольку последнее значение меньше, то НИЖПЯЯСВЯЗЬ[2] не меняется. Возвращаемся к вызову ПОИСКЕ (1), полагая НИЖНЯЯ-СВЯЗЬ[1]=МШ(1, НИЖНЯЯСВЯЗЫ2])=1. Исследовав далее ребро (1, 4), ничего не делаем, ибо (1,4) - прямое ребро, и условие строки 10 процедуры ПОИСКЕ не выполняется, так как 4>1.

Теперь вызываем ПОИСКЕ (5), и поперечное ребро (5, 4) вынуждает нас положить НИЖНЯЯСВЯЗЬ[5]=4, ибо 4<5 и 4 g СТЕК. Когда снова возвращаемся к вызову ПОИСКЕ (1), полагаем значение НИЖНЯЯСВЯЗЫ1] равным меньшему из чисел : 1 (предыдущее значение) и НИЖНЯЯСВЯЗЬ[5], т. е. НИЖНЯЯСВЯЗЫ1] = 1.

Затем, поскольку все ребра, выходящие из 1, уже рассмотрены и НИЖНЯЯСВЯЗЬ[1]=1, мы обнаруживаем, что 1 - корень сильно связной компоненты. Эта компонента состоит из 1 и всех узлов, находящихся в стеке выше 1. Так как узел 1 посещался первым, то узлы 2, 3, 4 и 5 находятся выше 1 и именно в этом по-

НИЖНЯЯСВЯЗЬ L1 ] = 1 (НИЖНЯЯСВЯЗЬ [6] = 6

"ЧННЖНЯЯСВЯЗЬ [5]= 4

НИЖНЯЯСВЯЗЬ [2] = 1 /



НИЖНЯЯСВЯЗЬ И = 6

- тшняясвязь [7] - ?

НИЖНЯЯСВЯЗЬ [З] = 1 НИЖНЯЯСВЯЗЬ [4] = 3

Рис. 5.16. Остовный лес с вычисленной функцией НИЖНЯЯСВЯЗЬ.



рядке. Поэтому стек опустошается и список узлов 1, 2, 3, 4, 5 печатается в качестве сильно связной компоненты графа G.

Другие сильно связные компоненты - это {7} и {6, 8}. Оставляем читателю закончить вычисление функции НИЖНЯЯСВЯЗЬ и сильно связных компонент, отправляясь от узла 6. Заметим, что последние встречи с корнями сильно связных компонент происходили в порядке 1, 7, 6. □

Теорема 5.4. Алгоритм 5.4 правильно находит сильно связные компоненты графа G за время 0(МАХ(«, е)), где п - число узлов, ае - число ребер ориентированного графа G.

Доказательство. Легко проверить, что на один вызов процедуры ПОИСКВ (и), не считая рекурсивных вызовов ПОИСКВ внутри этого вызова, тратится, кроме постоянного количества времени, время, пропорциональное числу ребер, выходящих из и. Поэтому все вызовы ПОИСКВ вместе занимают время, пропорциональное сумме количества узлов и количества ребер, поскольку ПОИСКВ вызывается только один раз для каждого узла. Участки алгоритма 5.4, отличные от процедуры ПОИСКВ, очевидно, можно реализовать за время 0(«). Тем самым оценка времени установлена.

Чтобы доказать корректность алгоритма, достаточно показать индукцией по числу тех вызовов процедуры ПОИСКВ, которые завершили работу, что по окончании ПОИСКВ (и) значение НИЖ-НЯЯСВЯЗЬ[и] вычислено правильно. После строк 12-16 процедуры ПОИСКВ узел v становится корнем сильно связной компоненты тогда и только тогда, когда НИЖНЯЯСВЯЗЬ[и]=и. Далее, в качестве результата печатаются в точности потомки узла и, не входящие в компоненты, корни которых были найдены раньше v (по лемме 5.8). А именно, узлы, находящиеся в стеке выше узла и, являются его потомками, а их корни не были найдены ранее и, поскольку эти узлы все еще находятся в стеке.

Чтобы доказать корректность вычисления функции НИЖНЯЯСВЯЗЬ, заметим, что на рис. 5.15 есть два места, где значение НИЖНЯЯСВЯЗЫи] могло быть меньше и; это строки 9 и 11 процедуры ПОИСКВ. В первом случае w - сын узла v и НИЖНЯЯ-СВЯЗЬ[ш1<и. Тогда некоторый узел л:=НИЖНЯЯСВЯЗЬ[ш] можно достичь из потомка у узла w через поперечное или обратное ребро. Кроме того, корень г сильно связной компоненты, содержащей X, является предком узла w. Поскольку x<.v, то r<t>, и, значит, г - подлинный предок узла v. Таким образом, значение НИЖ-НЯЯСВЯЗЬ[и] должно быть не больше, чем НИЖНЯЯСВЯЗЬ!»].

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



если бы г был слева от и, то вызов ПОИСКЕ (г) закончился бы.) Снова получаем, что значение НИЖНЯЯСВЯЗЬ[и] должно быть не больше w.

Осталось доказать, что ПОИСКВ вычисляет значение НИЖНЯЯ-СВЯЗЬ[и] столь малым, сколь оно должно быть. Допустим, что это не так, т. е. найдется предок х узла и, из которого в некоторый узел у идет поперечное или обратное ребро, а корень г сильно связной компоненты, содержащей у, является предком узла v. Надо показать, что НИЖНЯЯСВЯЗЫи] оказывается не больше у.

Случай 1. x=v. В силу предположения индукции и леммы 5.9 можно считать, что все сильно связные компоненты, найденные до сих пор, корректны. Тогда узел у все еще должен быть в СТЕКе, поскольку ПОИСКВ (/) еще не закончился. Следовательно, в строке И значение НИЖНЯЯСВЯЗЬ[и] полагается равным у или меньшему числу.

Случай 2. хфи. Пусть z - сын узла и, потомком которого является X. Тогда в силу предположения индукции по окончании вызова ПОИСКВ (z) значение НИЖНЯЯСВЯЗЬЫ должно быть равно у или меньшему числу. В строке 9 значение НИЖНЯЯ-СВЯЗЫи] становится именно таким, если раньше оно уже не было меньше. □

5.6. ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ

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

С задачей нахождения транзитивного замыкания графа тесно связана задача о кратчайшем пути. Поставим в соответствие каждому ребру е графа G неотрицательную стоимость с{е). Стоимость пути определяется как сумма стоимостей ребер, образующих его. Задача о кратчайшем пути состоит в нахождении для каждой пары узлов (и, 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.0038