Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 144
Текст из файла (страница 144)
Интересно замеппь, что графы С и Ст имеют одни и те же сильно связные компоненты: и и о достижимы одна из другой в С то~да и только тогда, когда они достижимы одна из другой в Ст. На рис. 22.9,(б) показан граф, представляюший собой результат транспонирования графа на рис. 22.9,(а) (сильно связные компоненты выделены штриховкой). Далее приведен алгоритм, который за линейное время тз(Ъ'+ Е) находит сильно связные компоненты ориентированного графа С = ($г, Е) благодаря двойному поиску в глубину: одному — в графе С и второму — в графе Ст.
Части КЕ Алгоритмы длл работы о графами БткОмб1х-СОмместеп-СОмРОмемтз (С) 1 Вызов РРБ(С) для вычисления времен завершения и.т для каждой вершины и 2 Вычисление Ст 3 Вызов РРБ(С~), но в основном цикле процедуры ПРБ вершины рассматриваются в порядке убывания значений и.1, вычисленных в строке 1 4 Вывод вершин каждого дерева в лесу поиска в глубину, полученного в строке 3, в качестве отдельного сильно связного компонента Идея, лежащая в основе этого алгоритма, опирается на ключевое свойство графа компонентов (сошропеш ягарЬ) СЕОО = ($'ЕОО, ЕЕОО), который определяется следующим образом.
Предположим, что С имеет сильно связные компоненты Сы Сз,..., Сы Множество вершин )г~~~ = (иы из,..., иь) содержит вершину гн для каждого сильно связного компонента С, графа С. Если в С имеется ребро (х,у) для некоторых двух вершин, х Е С, и у Е С, то в графе компонентов имеется ребро (мни ) Е ЕЗОО. другими словами, если сжать все ребра между смежными вершинами в каждом сильно связном компоненте графа С, мы получим граф С (вершинами которого являются сильно связные компоненты графа С). На рис. 22.9,(в) показан граф компонентов для графа, приведенного на рис.
22.9, (а). Ключевое свойство графа компонентов состоит в том, что он представляет собой ориентированный ациклический граф, как следует из приведенной ниже леммы. Лемма 22.13 Пусть С и С вЂ” различные сильно связные компоненты в ориентированном графе С = ()г Е) и пусть и, и е С и й, й е С', а кроме того, предположим, что в С имеется путь и и'. В таком случае в С не может быть пути й» и. Локазангельснгво. Если в С имеется путь й и, то в С имеются и пути и- и' » й и й - и - и. Следовательно, вершины и и й достижимы одна из другой, что противоречит предположению о том, что С н С' — различные сильно связные компоненты. Мы увидим, что при рассмотрении вершин в процессе второго поиска в глубину в порядке убывания времен завершения работы с вершинами, которые были вычислены при первом поиске в глубину, мы, по сути, посещаем вершины графа компонентов (каждая из которых соответствует сильно связному компоненту С) в порядке топологической сортировки.
Поскольку процедура Бткомпет-Сомместеп-СОМРОмемтз выполняет два поиска в глубину, имеется потенциальная неоднозначность при рассмотрении значений и. Н и и. г". В этом разделе данные значения всегда будут относиться ко времени открытия и времени завершения, вычисленным при первом вызове процедуры ПРБ в строке 1. Глава 22 Элементарные алгоритмы блл работы с графами 655 Мы распространим обозначения для времени открытия и времени завершения на множества вершин. Если У С 'и', то мы определим Н(У) = пйп„ап (и. ~Ц и 1(У) = шах,еп (иЯ, те. 4(У) н 1(У) представляют собой самое раннее время открытия и самое позднее время завершения соответственно для всех вершин в У.
Следующая лемма и следствие из нее описывают ключевое свойство, связывающее сильно связные компоненты и времена завершения, полученные при первом поиске в глубину. Л 22.1д Пусть С н С' — различные сильно связные компоненты в ориентированном графе С = (1', Е). Предположим, что имеется ребро (и, и) е Е, где и е С и и е С'. Тогда 1(С) > 1(С ). Докаэаявельсявво. Имеется два возможных случая в зависимости от того, какой нз сильно связных компонентов, С или С', содержит первую открытую в процессе поиска в глубину вершину. Если д(С) < д(С'), то обозначим как х первую открытую в С вершину. В момент времени х.
д все вершины в С и С' — белые. В С имеется путь от х к каждой вершине в С, состоящий только из белых вершин. Поскольку (и, и) е Е, для любой вершины ви Е С' в момент времени х. й в графе С имеется также путь от х к иг, состоящий только из белых вершин: х и — г и - ш. Согласно теореме о белом пути все вершины в С н С' становятся потомками х в дереве поиска в глубину. Согласно следствию 22.8 х имеет самое позднее время завершения по сравнению со всеми его потомками, так что х.1 = 1(С) > 1(С').
Если же Н(С) > Н(С'), то обозначим как у первую открытую вершину в С'. В момент у. и все вершины в С белые, и в С имеется путь от у к каждой вершине С', состоящий только из бельпе вершин. В соответствии с теоремой о белом пути все вершины в С' становятся потомками у в дереве поиска в глубину, так что согласно следствию 22.8 у.1 = 1'(С'). В момент времени у.
е( все вершины в С белые. Поскольку имеется ребро (и, и) из С в С', из леммы 22.13 вытекает, что не существует пути из С' в С. Следовательно, в С не имеется вершин, достижимых из у. Таким образом, в момент времени у.1 все вершины в С остаются белыми. Значит, для любой вершины иг т С имеем ш4 > у.1', откуда следует, что 1(С) > 1(С'). Приведенное ниже следствие говорит нам, что каждое ребро в Ст, соединяющее два сильно связных компонента, идет от компонента с более ранним временем завершения (при поиске в глубину) к компоненту с более поздним временем завершения.
Следствие 22.15 Пусть С и С' — различные сильно связные компоненты в ориентированном графе С = ($; Е). Предположим, что имеется ребро (и, и) е Ет, где и е С и и е С'. Тогда 1(С) ( 1(С'). Часть Р!. Алгоритмы длл работы с гра рами ббб Даказатевьство. Поскольку (и, и) й Ет, мы имеем (и, и) Е Е. Так как сильно связные компоненты С и Ст одни н те же, из леммы 22.14 следует, что 1'(С) < 1 1С'). Следствие 22.15 дает нам ключ к пониманию того, почему работает процедура Бтномоьт-Соммнстно-Сомромемтз.
Рассмотрим, что происходит, когда мы выполняем второй поиск в глубину над графом Ст. Мы начинаем с сильно связного компонента С, время завершения которого 1(С) максимально. Поиск начинается с некоторой вершины х е С, при этом посещаются все вершины в С. Согласно следствию 22.15 в Ст нет ребер из С в другой сильно связный компонент, так что при поиске из х не посещается ни одна вершина в других компонентах. Следовательно, дерево, корнем которого является х, содержит только вершины из С.
После того как будут посещены все вершины в С, поиск в строке 3 выбирает в качестве корня вершину из некоторого другого сильно связного компонента С', время завершения 1(С') которого максимально среди всех компонентов, отличных от С. Теперь поиск посещает все вершины в С'. Согласно следствию 22.15 в Ст единственным ребром из С' в другие компоненты может быть ребро в С, но этот компонент уже посещен. В общем случае, когда поиск в глубину в Ст в строке 3 посещает некоторый сильно связный компонент, все ребра, исходящие из этого компонента, должны идти в уже обработанные компоненты.
Следовательно, каждое дерево поиска в глубину является ровно одним сильно связным компонентом. Приведенная далее теорема формализует это доказательство. Теорема 22.1б Процедура Зткомо1.г-соммнстно-Сомроме1чтз(С) корректно вычисляет сильно связные компоненты ориентированного графа С. Доиазагаельсаьво. Воспользуемся индукцней по количеству найденных деревьев при поиске в глубину в Ст в строке 3 и докажем, что вершины каждого дерева образуют сильно связный компонент. Гипотеза индукции состоит в том, что первые к деревьев, полученных в строке 3, являются сильно связными компонентами.
Для базового случая /с = 0 это утверждение тривиально. Для выполнения шага индукции предположим, что каждое из первых Й деревьев поиска в глубину в строке 3 представляет собой сильно связный компонент, и рассмотрим (1с + 1)-е дерево. Пусть корнем этого дерева является вершина и и пусть и принадлежит сильно связному компоненту С.
В соответствии с тем, как мы выбираем корни при поиске в глубину в строке 3, для любого сильно связного компонента С', который еще не был посещен и отличен от С, справедливо соотношение и.1 = 11С) ) 1(С'). В соответствии с гипотезой индукции в момент времени, когда поиск посещает вершину и, все остальные вершины С вЂ” белые. Согласно теореме о белом пути все вершины С, кроме и, являются потомками и в дереве поиска в глубину. Кроме того, в соответствии с гипотезой индукции и со следствием 22.15 все ребра в Ст, которые покидают С, должны идти в уже посещенные сильно связные компоненты. Таким образом, ни в одном сильно связном Раааа 22.
Элеыентариые алгоритмы длл работы с графаыа 657 компоненте, отличном от С, нет вершины, которая бы стала потомком и в процессе поиска в глубину в Ст. Следовательно, вершины дерева поиска в глубину в С, корнем которого является и, образуют ровно один сильно связный компонент, что и завершает шаг индукции и доказательство данной теоремы. Вот еще одна точка зрения на работу второго поиска в глубину. Рассмотрим граф компонентов (СТ)ЗСС графа СТ. Если мы отобразим каждый сильно связный компонент, посещенный при втором поиске в глубину, на вершину (С~)зсс, то вершины этого графа компонентов при втором поиске в глубину посещаются в порядке, обратном топологической сортировке. Если мы обратим все ребра графа (Ст)зсс,то получим 1раф ((Ст)зсс)т 1ак как ((Ст)асс)т Сзсс (см.
упр. 22.5.4), при втором поиске в глубину вершины Свсс посещаются в порядке топологической сортировки. Упражнения 22.5.1 Как может измениться количество сильно связных компонентов графа при добавлении в граф нового ребра? 22.5.2 Покажите, как процедура Бткомси'-Соннвстн)-Сомрснвмтз работает с графом, показанным на рис. 22.6. В частности, определите время завершения, вычисляемое в строке 1, и лес, полученный в строке 3. Считаем, что цикл в строках 5-7 процедуры РРЗ рассматривает вершины в алфавитном порядке и что так же упорядочены и списки смежности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
