1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 44
Текст из файла (страница 44)
Эта проверка осуществляется с помощью массива, указывающего наличие узла в стеке. Заметим, что по лемме 5.8 если ю еще в стеке, то корень сильно связной компоненты, содержащей и, является предком узла о. Изложим модификацию процедуры ПОИСК, которая вычисляет функцию НИЖНЯЯСВЯЗЬ. Она использует магазинный список СТЕК для узлов. Эта процедура приведена на рис. 5.15. Функция НИЖНЯЯСВЯЗЬ вычисляется в строках 4, 9 и 11.
В строке 4 в качестве начального значения для НИЖНЯЯСВЯЗЬ[о) берется номер узла и, присвоенный ему поиском в глубину. В строке 9 полагаем НИЖНЯЯСВЯЗЬЫ=НИЖНЯЯСВЯЗЬЫ, если для некоторого сына ш узел НИЖНЯЯСВЯЗЬЫ оказался меньше текущего значения НИЖНЯЯСВЯЗЬЫ. В строке 1О узнаем, является (о, ш) обратным или поперечным ребром, и проверяем, не найдена ли уже сильно связная компонента, содержащая пА Если нет, то корень сильно связной компоненты, содержащей ш, будет предком узла о.
По необходимости полагаем в строке ! 1 значение НИЖНЯЯСВЯЗЬ[п] равным номеру узла и, присвоенному ему поиском в глубину, если оно раньше не получило меньшее значение. Теперь сформулируем весь алгоритм нахождения сильно связных компонент ориентированного графа. 219 гл. а. Алгоритмы ИА ГРАФАХ ргоседпге ПОИСКВ(о): Ьея) п 1. пометить узел в как "старый"; 2. ПГНОМЕР[о) -СЧЕТ; 3.
СЧЕТ вЂ” СЧЕТ-1-1; 4. НИЖНЯ ЯСВЯЗЬ[о] — ПГНОМЕР[о~; 5. затолкнуть и в СТЕК; 6. 1ог вЕЦо~ до 7. Н узел в помечен как "новый" !Ьеп Ьед! п 8, ПОИСКВ(в); 9. НИЖНЯЯСВЯЗЬ[о~ -М!Ы(НИЖНЯЯСВЯЗЬ[о~, НИЖНЯЯСВЯЗЬЩ епд е!зе Н ПГНОМЕР[в) < ПГНОМЕР[в) и вЕСТЕК ЧЬеп НИЖНЯЯСВЯЗЬ[о) -М1Ы(ПГНОМЕР[в1, НИЖНЯЯСВЯЗЬ[о)); 12. Н НИЖНЯЯСВЯЗЬ[о1=ПГНОМЕР[о1 Гйеп Ьеа)п гереа1 Ьей1п вытолкнуть х из вершины СТЕКа; рг)п! к епд 15. нпГН х=о; 15. рг1п1 "конец сильно связной компоненты" епд епс) 10 11 13 !4 Рис.
5ЛВ. Процедура для вычисления функции НИЖНЯЯСВЯЗЬ. Вход. Ориентированный граф б= (к', Е). Выход. Список сильно связных компонент графа б. Алгоритм 5,4. Нахождение сильно связных компонент ориентиро- ванного графа 5.5, сильнАя связность Метод. Ьей]п СЧЕТ -1; 1ог ВЕ'и' до пометить узел и как "новый"; сделать СТЕК пустым; тв]ь!]е существует узел и, помеченный как "новый" до ПОИСКВ(п! епд [:] Пример 5.8. Рассмотрим глубинный остовный лес на рнс. 5.!3. Этот лес воспроизведен на рис. 5.15, где указаны также значения функции НИЖНЯЯСВЯЗЬ. Вызов ПОИСКВ(3) заканчивает работу первым среди всех вызовов процедуры ПОИСКВ. Когда мы исследуем ребро(3,!), полагаем НИЖНЯЯСВЯЗЬ[3]=М]5](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) — прямое ребро, и условие строки !О процедуры ПОИСКВ не выполняется, так как 4 -1. Теперь вызываем ПОИСКВ (5), и поперечное ребро (5, 4) вынуждает нас положить НИЖНЯЯСВЯЗЫ5]=4, ибо 44 '5 и 4ЕСТЕК. Когда снова возвращаемся к вызову ПОИСКВ(1), полагаем значение НИЖНЯЯСВЯЗЬ[1] равным меньшему из чисел: 1 (предыдущее значение) и НИЖНЯЯСВЯЗЬ[5], т. е. НИЖНЯЯСВЯЗЬ[1]=!. Затем, поскольку все ребра, выходящие из 1, уже рассмотрены и НИЖНЯЯСВЯЗЬН]=1, мы обнаруживаем, что 1 — корень сильно связной компоненты.
Эта компонента состоит из ! и всех узлов, находящихся в стеке выше 1. Так как узел 1 посещался первым, то узлы 2, 3, 4 и 5 находятся выше ! и именно в этом по- иижияясвязь !6] 6 ЗЬ !6]~4 — — 7 — 8 иивнввсвязь [а! б инииивсвввь !т! - т веаяясввзь 55 = 5 вввлввсввзь (4! 3 Рис. йдб. Остовннй лес с вычисленной фунвиией НИЖНЯЯСВЯЗЪ, 22$ Гл.
а АЯГОРитмы ИА ГРАФАХ рядке. Поэтому стек опустошается и список узлов 1, 2, 3, 4, 5 печатается в качестве сильно связной компоненты графа О. Другие сильно связные компоненты — это (7) и (6, 8). Оставляем читателю закончить вычисление функции НИЖНЯЯСВЯЗЬ н сильно связных компонент, отправляясь от узла 6. Заметим, что последние встречи с корнями сильно связных компонент происходили в порядке 1, 7, 6. С) Теорема 5.4.
Алгоритм 5.4 правильно находит сильно связные компоненты графа 0 за время 0(МАХ (и, е)), где п — число узлов, а е — число ребер ориентированного графа О, До к а з а т ел ь с т в о. Легко проверить, что на один вызов процедуры ПОИСКВ (о), не считая рекурсивных вызовов ПОИСКВ внутри этого вызова, тратится, кроме постоянного количества времени, время, пропорциональное числу ребер, выходящих из и. Поэтому все вызовы ПОИСКВ вместе занимают время, пропорцио. иальное сумме количества узлов и количества ребер, поскольку ПОИСКВ вызывается только один раз для каждого узла.
Участки алгоритма 5.4, отличные от процедуры ПОИСКВ, очевидно, можно реализовать за время 0(п). Тем самым оценка времени установлена. Чтобы доказать корректность алгоритма, достаточно показать индукцией по числу тех вызовов процедуры ПОИСКВ, которые завершили работу, что по окончании ПОИСКВ(п) значение НИЖНЯЯСВЯЗЬ[п! вычислено правильно. После строк 12 — 16 процедуры ПОИСКВ узел и становится корнем сильно связной компоненты тогда и только тогда, когда НИЖНЯЯСВЯЗЬЫ=п.
Далее, в ычестве результата печатаются в точности потомки узла и, ие входящие в компоненты, корни которых были найдены раньше и (по лемме 5.8). А именно, узлы, находящиеся в стеке выше узла в, являются его потомками, а их корни не были найдены ранее и, поскольку эти узлы все еще находятся в стеке. Чтобы доказать корректность вычисления функции НИЖНЯЯ- СВЯЗЬ, заметим, что на рис. 5.15 есть два места, где значение НИЖНЯЯСВЯЗЬЫ могло быть меньше и; это строки 9 и !1 про.
цедуры ПОИСКВ. В первом случае ш — сын узла и и НИЖНЯЯСВЯЗЬ[ш)(о. Тогда некоторый узел х=НИЖНЯЯСВЯЗЬЫ можно достичь из потомка у узла ш через поперечное или обратное ребро. Кроме того, корень Г сильно связной компоненты, содержащей х, является предком узла ш. Поскольку х~п, то Г<п, и, значит, à — подлинный предок узла и. Таким образом, значение НИЖНЯЯСВЯЗЬ[и! должно быть не больше, чем НИЖНЯЯСВЯЗЬ[м!. Во втором случае — в строке 11 — из и идет поперечное или обратное ребро в узел ы~ и, сильно связная компонента С которого еще не найдена. Вызов процедуры ПОИСКВ на корне Г из С еще ие закончился, так что Г должен быть предком узла о.
(Так как Г~вСо, то либо г лежит слева от и, либо г — предок узла о. Но их ь. злдлчи нлхождания питая если бы г был слева от о, то вызов ПОИСКВ (г) закончился бы.) Снова получаем, что значение НИЖНЯЯСВЯЗЬ(о! должно быть не больше и. Осталось доказать, что ПОИСКВ вычисляет значение НИЖНЯЯСВЯЗЪ)о) столь малым, сколь оно должно быть. Допустим, что это не так, т. е.
найдется предан х узла о, из которого в некоторый узел у идет поперечное или обратное ребро, а корень г сильно связной компоненты, содержащей у, является предком узла о. Надо показать, что НИЖНЯЯСВЯЗЫо] оказывается не больше у. Случай 1. х=о. В силу предположения индукции и леммы 5.9 можно считать, что все сильно связные компоненты, найденные до сих пор, корректны.
Тогда узел у все еще должен быть в СТЕКе, поскольку ПОИСКВ(г) еще не закончился. Следовательно, в стропе П значение НИЖНЯЯСВЯЗЫо) полагается равным у или меньшему числу. Случай 2. х~о. Пусть г — сын узла о, потомком которого является х. Тогда в силу предположения индукции по окончании вызова ПОИСКВ (г) значение НИЖНЯЯСВЯЗЪ)г) должно быть равно у или меньшему числу. В строке 9 значение НИЖНЯЯСВЯЗЫо) становится именно таким, если раньше оно уже не было меньше. С) 5.6.
ЗАДАЧИ НАХОЖДЕНИЯ ПУТЕЙ В этом разделе мы изучим две часто встречающиеся задачи, касающиеся путей, соединяющих узлы. В дальнейшем 6 будет ориентированным графом. (Рефлексивным и) транзитивным замыканием графа 6 называется граф 6*, который содержит то же множество узлов, что и 6, но в нотором из о в ш идет ребро тогда и только тогда, когда в 6 существует путь (длины О или больше) из о в ил С задачей нахождения транзитивного замыкания графа тесно связана задача о кратчайшем пути. Поставим в соответствие каждому ребру е графа 6 неотрицательную стоимость с(е). Стоимосгпь пути определяется как сумма стоимостей ребер, образующих его. Задача о кратчайшем пути состоит в нахождении для каждой пары узлов (о, ю) пути наименьшей стоимости среди всех путей из о в ш.
Оказывается, что идеи, на которых основаны лучшие из известных алгоритмов нахождения транзитивного замынания и кратчайшего пути, являются (простыми) частными случаями соображений, исходя из которых решается задача нахождения (бесконечного) множества всех путей между каждой парой узлов. Чтобы обсудить эту задачу во всей ее общности, введем специальную алгебраическую структуру.
Определение. Замкнутым полукольцом называется система Гл. а АлГОРитмы ИА ГРАФАХ (5,+,, О, 1), где 5 — множество элементов, а + и ° — бинарные операции на 5, обладающие следующими пятью свойствами: 1) (5, +, 0) — моноид, т. е. множество 5 замкнуто относительно + (а+ЬЕ5 для всех а и Ь из 5), операция + ассоциативна (а+(Ь+с)= (а+Ь)+с для всех а, Ь, с из 5) и 0 служит единичным элементом (а+0=0+а=а для всех а из 5).
Тройка (5,, !) также является моноидом. Кроме того, мы предполагаем, что 0 служит аннуллтором, т. е. а ° 0=0 ° а=О. 2) Операция + коммутатизна (а+Ь=Ь+а) и идемпотентна (а+а=а). 3) Операция ° дистрибутивна относительно+(а (Ь+с)=а ° Ь+ +а ° с и (Ь+с) ° а=Ь ° а+с а): 4) Если аь а„..., а„... — счетная последовательность элементов из 5, то сумма а,+а,+...+а,+...
существует и единственна. Более того, ассоциативность, коммутативнос!ь и идемпотентность выполняются не только для конечных, но и для бесконечных сумм. 5) Операция ° дистрибутивна не только относительно конечных сумм, но и относительно счетных (это не следует из свойства 3), Таким образом, из свойств 4 и 5 вытекает, что (~~'„а,) ° (~РЬ~) = ~(а! Ь,) =~~~~ ~Я (а, Ь|)) . О ! о 1 ! ! о О О ! Свойства 1 — 3 проверить легко. Что касается свойств 4 н 5, то заметим, что счетная сумма равна 0 тогда и только тогда, когда все слагаемые равны О. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
