Алгоритмы - построение и анализ (1021735), страница 129
Текст из файла (страница 129)
Если вершина ц — белая, то она становится потомком и, так что Г" [ц] < г" [и]. Если ц — черная, значит, работа с ней уже завершена и значение 7' [о] уже установлено. Поскольку мы все еше работаем с вершиной и, значение Г" [и] еще не определено, так что, когда это будет сделано, будет выполняться неравенство Г" [ц] < Г' [и]. Следовательно, для любого ребра (и, ц) ориентированного ациклического графа выполняется условие 7 [с] < 1 [и], что и доказывает данную теорему. И Упражнения 22.4-1. Покажите, в каком порядке расположит вершины представленного на рис. 22.8 ориентированного ациклического графа процедура Товоьос!ель Болт, если считать, что цикл 1ог в строках 5-7 процедуры 13РБ сканирует вершины в алфавитном порядке, а также что все списки смежности упорядочены по алфавиту.
22.4-2. Разработайте алгоритм с линейным временем работы, который для данного ориентированного ациклического графа С = (Ъ; Е) и двух вершин Глава 22. Элементарные алгоритмы для работы с графами 635 з и г определяет количество путей из а к 1 в графе С. Например, в графе на рис.
22.8 имеется ровно 4 пути от вершины р к вершине гл ров, ромул, роагре и рапге. Ваш алгоритм должен только указать количество путей, не перечисляя их. 22.4-3. Разработайте алгоритм для определения, содержит ориентированный граф С = (У,Е) цикл или нет. Ваш алгоритм должен выполняться за время О (У), независимо от 1Е~. 22.4-4. Докажите или опровергните следующее утверждение: если ориентированный граф С содержит циклы, то процедура Того1.осси. Бокт(С) упорядочивает вершины таким образом, что при этом количество "плохих" ребер (идущих в противоположном направлении) минимально.
22.4-5. Еще один алгоритм топологической сортировки ориентированного ациклического графа С = (У, Е) состоит в поиске вершины со входящей степенью О„выводе ее, удалении из графа этой вершины и всех исходящих из нее ребер, и повторении этих действий до тех пор, пока в графе остается хоть одна вершина. Покажите, как реализовать описанный алгоритм, чтобы время его работы составляло О (У + Е). Что произойдет, если в графе С будут иметься циклы? 22.5 Сильно связные компоненты Теперь мы рассмотрим классическое применение поиска в глубину: разложение ориентированного графа на сильно связные компоненты.
В этом разделе будет показано„как выполнить такое разложение при помощи двух поисков в глубину. Ряд алгоритмов для работы с графами начинаются с выполнение такого разложения графа, и после разложения алгоритм отдельно работает с каждым сильно связным компонентом. Полученные решения затем комбинируются в соответствии со структурой связей между сильно связными компонентами.
В приложении Б сказано, что сильно связный компонент ориентированного графа С = (У, Е) представляет собой максимальное множество вершин С С У, такое что для каждой пары вершин и и о из С справедливо как и - е, так и о -» и, т.е. вершины и и о достижимы друг из друга. На рис. 22.9 приведены примеры сильно связных компонентов. Наш алгоритм поиска сильно связных компонентов графа С = (У, Е) использует транспонирование С, которое определяется в упражнении 22.1-3 как граф Ст = (У,Е ), где Е = ((и,е): (п,и) еЕ), т.е. Е состоит из ребер С путем изменения их направления на обратное.
Для представления с помощью списков смежности данного графа С получить граф Ст можно за время О (У+ Е). Интересно заметить, что графы С и Ст имеют одни и те же сильно связные компоненты: и и о достижимы друг из друга в С тогда и толью тогда, югда они Часть Ч1. Алгоритмы для работы с графами 636 а... ь с )ЭВ6936Ю )' [ Рис. 22.9. Сильно связные компоненты ориентирован- ного графа достижимы друг из друга в Ст. На рис. 22.9б показан граф, представляющий собой результат транспонирования графа на рис. 22.9а (сильно связные компоненты выделены штриховкой). Далее приведен алгоритм, который за линейное время б1($'+ Е) находит сильно связные компоненты ориентированного графа С = (Ч Е) благодаря двойному поиску в глубину, одному — в графе С, и второму — в графе СТ.
БткОхОеу СОххесте0 СОмРОхехтз(С) 1 Вызов 13ГБ(С) для вычисления времен завершения 1[и] для каждой вершины и 2 Построение СТ 3 Вызов )ЗРИМ(С~), но в главном цикле процедуры 0ГБ, вершины рассматриваются в порядке убывания значений г"[и] вычисленных в строке 1 4 Деревья леса поиска в глубину, полученного в строке 3 представляют собой сильно связные компоненты Идея, лежащая в основе этого алгоритма, опирается на ключевое свойство графа компонентов (сошропеп1 ятарЬ) Се~~ = (Ъ'е~~, Ез~~), который определяется Глава 22. Элементарные алгоритмы для работы с графами 637 следующим образом. Предположим, что С имеет сильно связные компоненты Сы Сз,..., Ся.
Множество вершин Ъ'~~~ = (оы пз,..., оь) состоит из вершин и, для каждого сильно связного компонента С; графа С. Если в С имеется ребро (х, у) для некоторых двух вершин х е С; и у е Су, то в графе компонент имеется ребро (о;, и ) е ЕаОО. другими словами, если сжать все ребра между смежными вершинами в каждом сильно связном компоненте графа С, мы получим граф С~~~ (вершинами которого являются сильно связные компоненты графа С). На рис. 22.9в показан граф компонентов для графа, приведенного на рис. 22,9а. Ключевое свойство графа компонентов заключается в том, что он представляет собой ориентированный ациклический граф, как следует из приведенной ниже леммы. Лемма 22.13.
Пусть С и С' — различные сильно связные компоненты в ориентированном графе С = (Ъ; Е), и пусть и, о е С и и',о' е С', а кроме того, предположим, что в С имеется путь и - и'. В таком случае в С не может быть пути и > и. Доказательсгиво. Если в С имеется путь и' - и, то в С имеются и пути пи' - и' и и' - п - и. Следовательно, вершины и и и' достижимы одна из другой, что противоречит предположению о том, что С и С' — различные сильно связные компоненты, Мы увидим, что при рассмотрении вершин в процессе второго поиска в глубину в порядке убывания времен завершения работы с вершинами, которые были вычислены при первом поиске в глубину, мы по сути посещаем вершины графа компонентов (каждая из которых соответствует сильно связному компоненту С) в порядке топологической сортировки. Поскольку процедура ЯТКОМОЬТ СОИХЕСТЕО СОМРОИЕХТБ выполняет два поиска в глубину, имеется потенциальная неоднозначность при рассмотрении значений И ~и) и г" (и].
В этом разделе данные значения будут относиться исключительно к времени открытия и времени завершения, вычисленным при первом вызове процедуры РРБ в строке 1. Мы распространим обозначения для времени открытия и времени завершения на множества вершин. Если У С У, то мы определим о(У) = ппп„вп (Н~и)) и г" (У) = шах„еп(г" Щ, т.е. Н(У) и г'(У) представляют собой самое раннее время открытия и самое позднее время завершения для всех вершин в У.
Следующая лемма и следствие из нее описывают ключевое свойство, связывающее сильно связные компоненты и времена завершения, полученные при первом поиске в глубину. Часть Ч]. Алгоритмы для работы с графами 638 Лемма 22.14. Пусть С и С' — различные сильно связные компоненты в ориентированном графе С = (К Е). Предположим, что имеется ребро (и, и) Е Е, где и Е С и и Е С'. Тогда г' (С) > г (С').
Доказательства. Имеется два возможных случая в зависимости от того, какой вз сильно связных компонентов, С или С', содержит первую открытую в процессе поиска в глубину вершину. Если Н(С) < Н(С'), то обозначим первую открытую в С вершину как х. В момент времени Н [х] все вершины в С и С' — белые. В С имеется путь от х к каждой вершине в С, состоящий только из белых вершин. Поскольку (и, и) е Е, для любой вершины и~ Е С' в момент времени Н [х] в графе С имеется также путь от х к и, состоящий только из белых вершин: х - и и -» и. Согласно теореме о белом пути, все вершины в С и С' становятся потомками х в дереве поиска в глубину.
Согласно следствию 22.8, г" [х] = )'(С) > 1'(С'). Если же Н (С) > Ы (С'), то обозначим первую открытую вершину в С' как у. В момент Н [у] все вершины в С' белые, и в С имеется путь от у к каждой вершине С', состоящий только из белых вершин. В соответствии с теоремой о белом нуги, все вершины в С' становятся потомками у в дереве поиска в глубину, так что согласно следствию 22.8, 1 [у] = Г (С'). В момент времени с1 [у] все вершины в С белые.
Поскольку имеется ребро (и, и) из С в С', из леммы 22.13 вытекает, что не существует пути из С' в С. Следовательно, в С не имеется вершин, достижимых из у. Таким образом, в момент времени 1 [у] все вершины в С остаются белыми. Значит, для любой вершины и Е С имеем г" [ш] > У [у], откуда следует, что г" (С) > > г" (С'). И Приведенное ниже следствие говорит нам, что каждое ребро в Ст, соединяющее два сильно связных компонента, идет от компонента с более ранним временем завершения (при поиске в глубину) к компоненту с более поздним временем завершения.
Следствие 22.15. Пусп С и С' — различные сильно связные компоненты в ориентированном графе С = (У, Е). Предположим, что имеется ребро (и, и) е Ет, где и Е С и и е С'. Тогда г" (С) < У (С'). Доказательства Поскольку (и, и) Е Е г, (и, и) Е Е. Так как сильно связные компоненты С и Ст одни и те же, из леммы 22.14 следует, что г" (С) < г" (С'). м Следствие 22.15 дает нам ключ к пониманию того, как работает процедура Ятконях Сомннстю Сомромннтз. Рассмотрим, что происходит, когда мы выполняем второй поиск в глубину над графом Ст. Мы начинаем с сильно связного компонента С, время завершения которого г" (С) максимально.
Поиск начинается с некоторой вершины х б С, при этом посещаются все вершины в С. Согласно Глава 22. Элементарные алгоритмы для работы с графами 639 следствию 22.15, в Ст нет ребер от С к другому сильно связному компоненту, так что при поиске из х не посещается ни одна вершина в других компонентах. Следовательно, дерево, корнем которого является х, содержит только вершины из С. После того как будут посещены все вершины в С, поиск в строке 3 выбирает в качестве корня вершину из некоторого другого сильно связного компонента С', время завершения 1 (С') которого максимально среди всех компонентов, исключая С.
Теперь поиск посещает все вершины в С'. Согласно следствию 22.15, в Ст единственным ребром из С' в другие компоненты может быть ребро в С, но обработка компонента С уже завершена. В общем случае, когда поиск в глубину в Ст в строке 3 посещает некоторый сильно связный компонент, все ребра, исходящие из этого компонента, идут в уже обработанные компоненты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
