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


Рнс. 5.14. Поперечное ребро, удовлетворяющее условию из определения функции

нижняясвязь.

Лемма 5.9. Пусть G - ориентированный граф. Для того чтобы узел V был корнем сильно связной компоненты графа О, необходимо и достаточно, чтобы НИЖНЯЯСВЯЗЬЫ=и.

Доказательство. Необходимость. Пусть v - корень сильно связной компоненты графа G. По определению НИЖНЯЯ-СВЯЗЬ[о]<у. Допустим, что НИЖНЯЯСВЯЗЬЫ<у. Тогда найдутся такие узлы тяг, что

1) в W входит поперечное или обратное ребро, выходящее из потомка узла v,

2) г - корень сильно связной компоненты, содержащей w,

3) г - предок узла у,

4) uxiv.

По условию 2 г - предок узла w, так что rw. Следовательно, по условию 4 r<.v, откуда в силу условия 3 вытекает, что г - подлинный предок узла v. Wo г я v должны принадлежать одной и той же сильно связной компоненте, поскольку в G идут пути из гвуиизувг через w. Поэтому v не корень сильно связной компоненты-, получили противоречие. Таким образом, НИЖНЯЯ-СВЯЗЬ[у]=у.

Достаточность. Пусть НИЖНЯЯСВЯЗЬ[у]=у. Если v - не корень сильно связной компоненты, содержащей v, то корнем будет некоторый подлинный предок г узла v. Следовательно, есть путь Я из у в г. Рассмотрим первое ребро в Я, идущее из потомка узла у в узел w, не являющийся потомком узла у. Это ребро либо обратное и идет к предку узла у, либо поперечное и идет в узел, номер которого меньше у. В любом случае ш<;у.

Осталось показать, что г яш принадлежат одной и той же сильно связной компоненте графа G. Из л в у должен идти путь, поскольку г - предок узла у. Путь Я идет из у через w в г. Следовательно,



Г Я W принадлежат одной и той же сильно связной компоненте. Таким образом, НИЖНЯЯСВЯЗЬ[уК!:г)<у; получили противоречие. □

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

Попав в узел v в первый раз, полагаем НИЖНЯЯСВЯЗЬ[у]=у. Когда встречается обратное или поперечное ребро (у, w) и w принадлежит той же сильно связной компоненте, что и некоторый предок узла v, то полагаем значение функции НИЖНЯЯСВЯЗЬ в узле V равным меньшему из двух чисел: ее текущего значения и w. Когда встречается древесное ребро (у, w), рекурсивно просматривается поддерево с корнем w и вычисляется НИЖНЯЯСВЯЗЬ[!11]. По возвращении к у значение функции НИЖНЯЯСВЯЗЬ в узле у полагается равным меньшему из чисел: ее текущего значения и

нижняясвязьы.

Чтобы проверить, принадлежит ли w той же компоненте, что и некоторый предок узла у, достаточно посмотреть, находится ли еще узел w в стеке для узлов. Эта проверка осуществляется с помощью массива, указывающего наличие узла в стеке. Заметим, что по лемме 5.8 если w еще в стеке, то корень сильно связной компоненты, содержащей w, является предком узла у.

Изложим модификацию процедуры ПОИСК, которая вычисляет функцию НИЖНЯЯСВЯЗЬ. Она использует магазинный список СТЕК для узлов. Эта процедура приведена на рис. 5.15.

Функция НИЖНЯЯСВЯЗЬ вычисляется в строках 4, 9 и П. в строке 4 в качестве начального значения для НИЖНЯЯСВЯЗЬ[у] берется номер узла у, присвоенный ему поиском в глубину. В строке 9 полагаем НИЖНЯЯСВЯЗЬ[у]=НИЖНЯЯСВЯЗЬЫ, если для некоторого сына w узел НИЖНЯЯСВЯЗЬ[ш] оказался меньше текущего значения НИЖНЯЯСВЯЗЬМ. В строке 10 узнаем, является (у, w) обратным или поперечным ребром, и проверяем, не найдена ли уже сильно связная компонента, содержащая w. Если нет, то корень сильно связной компоненты, содержащей w, будет предком узла у. По необходимости полагаем в строке 11 значение НИЖНЯЯСВЯЗЬ[у] равным номеру узла w, присвоенному ему поиском в глубину, если оно раньше не получило меньшее значение.

Теперь сформулируем весь алгоритм нахождения сильно связных компонент ориентированного графа.



procedure ПОИСКЕ (у): begin

1. пометить узел v как "старый";

2. ПГНОМЕР[у] -СЧЕТ;

3. СЧЕТ СЧЕТ+ 1;

4. НИЖНЯЯСВЯЗЬ[у] -ПГНОМЕРМ;

5. затолкнуть v в СТЕК;

6. for wL[v] do

7. if узел w помечен как "новый" then

begin

8. ПОИСКВИ;

9. НИЖНЯЯСВЯЗЬИ МШ(НИЖНЯ ЯСВ ЯЗЬ[у],

НИЖНЯЯСВЯЗЬ)

end else

iO. if ПГНОМЕРМ < ПГНОМЕР[у] и о; е СТЕК then

i 1. НИЖНЯЯСВ ЯЗЬ[у] *- МШ(ПГНОМЕРН,

НИЖНЯЯСВЯЗЬИ);

12. if НИЖНЯЯСВЯЗЬ[у] = ПГНОМЕР[у] then

begin repeat begin

13. вытолкнуть X из вершины СТЕКа;

14. print X end

15. until x = v;

16. print "конец сильно связной компоненты" end

Рис. 5.15. Процедура для вычисления функции НИЖНЯЯСВЯЗЬ.

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

Вход. Ориентированный граф G={V, Е).

Выход. Список сильно связных компонент графа G.





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