Алгоритмы - построение и анализ (1021735), страница 130

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 130)

Следовательно„ каждый поиск в глубину обрабатывает ровно один сильно связный компонент. Приведенная далее теорема формализует это доказательство. Теорема 22.16. Процедура Ятиоыои' Со]чместпо Сомроынчтз(С) корректно вычисляет сильно связные компоненты ориентированного графа С. Доказатвльсогво. Воспользуемся индукцией по количеству найденных деревьев при поиске в глубину в Ст в строке 3, и докажем, что вершины каждого дерева образуют сильно связный компонент. Гипотеза индукции состоит в том, что первые й деревьев, полученные в строке 3, являются сильно связными компонентами.

Для случая й = О это утверждение тривиально. Для выполнения шага индукции предположим, что каждое из первых й деревьев поиска в глубину в строке 3, представляет собой сильно связный компонент, и рассмотрим (/с + 1)-е дерево. Пусть корнем этого дерева является вершина и, и пусть и принадлежит сильно связному компоненту С. В соответствии с тем как мы выбираем корни при поиске в глубину в строке 3, для любого сильно связного компонента С', который еще не был посещен и отличен от С, справедливо соотношение Г" ~и] = Г" (С) ) Г" (С'). В соответствии с гипотезой индукции в момент времени, когда поиск посещает вершину и, все остальные вершины С вЂ” белые. Согласно теореме о белом пути, все вершины С, кроме и, являются потомками и в дереве поиска в глубину.

Кроме того, в соответствии с гипотезой индукции и со следствием 22.15, все ребра в Ст, которые покидают С, должны идти в уже посещенные сильно связные компоненты. Таким образом, ни в одном сильно связном компоненте, отличном от С, нет вершины, которая бы стала потомком и в процессе поиска в глубину в Ст. Следовательно, вершины дерева поиска в глубину в Ст, корнем которого является и, образуют ровно один сильно связный компонент, что и завершает шаг индукции и доказательство данной теоремы. Вот еще одна точка зрения на работу второго поиска в глубину.

Рассмотрим граф компонентов (Ст)ЗОО графа Ст. Если мы отобразим каждый сильно связный компонент, посещенный при втором поиске в глубину, на вершину (Ст)зоо, Часть Ч1. Алгоритмы для работы с графами то вершины этого графа компонентов посещаются в порядке, обратном топологической сортировке.

Если мы обратим все ребра графа (Ст)аоо, то получим граф ИСт)КОС)т Так как (1Ст)ЯСС)т Сзсс (см упражнение 22 5 4) при втором поиске в глубину вершины Саоо посещаются в порядке топологической сортировки. Упражнения 22.5-1. Как может измениться количество сильно связных компонентов графа при добавлении в граф нового ребра? 22.5-2. Рассмотрите работупроцедуры Бткохаи' Соьлчестео Сомюмемтз над графом, показанным на рис. 22.6. В частности, определите время завершения„вычисляемое в строке 1, и лес, полученный в строке 3.

Считаем, что цикл в строках 5-7 процедуры ОРБ рассматривает вершины в алфавитном порядке и что так же упорядочены и списки смежности. 22.5-3. Профессор считает, что алгоритм определения сильно связных компонентов можно упростить, если во втором поиске в глубину использовать исходный, а не транспонированный граф, и сканировать вершины в порядке возрастания времени завершения. Прав ли профессор? 22.5-4. Докажите, что для любого ориентированного графа С справедливо соотношение ИС~) оо) = С~~~, т.е.

что транспонирование графа компонентов СТ дает граф компонентов графа С. 22.5-5. Разработайте алгоритм, который за время 0 ('и'+ Е) находит граф компонентов ориентированного графа С = (1г, Е). Убедитесь, что в полученном графе компонентов между двумя вершинами имеется не более одного ребра. 22.5-6.

Поясните, как для данного ориентированного графа С = ('1Г,Е) создать другой граф С' = ('и',Е'), такой что а) С' имеет те же сильно связные компоненты, что и С, б) С' имеет тот же граф компонентов, что и С, и в) Е' имеет минимально возможный размер. Разработайте быстрый алгоритм для вычисления С'. 22.5-7. Ориентированный граф С = ('и", Е) называется палусаязным (зеш1соллес1ед), если для всех пар вершин и, ц Е Ъ' и ц или е - и (или и то, и другое одновременно). Разработайте эффективный алгоритм для определения, является ли данный граф С полусвязным. Докажите корректность разработанного алгоритма и проанализируйте время его работы. Глава 22. Элементарные алгоритмы для работы с графами Задачи 22-1.

Классификация ребер при поиске в ширину Лес поиска в глубину позволяет классифицировать ребра графа как ребра деревьев, обратные, прямые и перекрестные. Дерево поиска в ширину также можно использовать для аналогичной классификации ребер, достижимых из исходной вершины. а) Докажите, что при поиске в ширину в неориентированном графе выполняются следующие свойства. 1) Не существует прямых и обратных ребер. 2) Для каждого ребра дерева (и, и) имеем г( [и] = г( [и) + 1.

3) Для каждого перекрестного ребра (и, и) имеем г( [и] = г( [и) или 0[и) = И[и)+ 1. б) Докажите, что при поиске в ширину в ориентированном графе выполняются следующие свойства. 1) Не существует прямых ребер. 2) Для каждого ребра дерева (и, о) имеем д [и] = г( [и) + 1. 3) Для каждого перекрестного ребра (и, и) имеем г1 [и] < г( [и] + 1. 4) Для каждого обратного ребра (и, и) имеем 0 < и' [и] < г( [и]. 22-2.

Точки сочленения, мосты и двусвязиые компоненты Пусть С = ((г, Е) — связный неориентированный граф. Точкой сочленения (агйси1айоп ро(пг) С называется вершина„удаление которой делает граф несвязным. Мостом (Ьг(дде) графа С называется ребро, удаление которого делает граф несвязным. Двусвязяый компонент (Ь1соппесгег( сошропепг) графа С представляет собой максимальное множество ребер, такое что любые два ребра этого множества принадлежат общему простому циклу. На рис. 22.10 проиллюстрированы приведенные определения.

Темным цветом на рисунке выделены точки сочленения и мосты, двусвязные компоненты — наборы ребер в пределах одной серой области (внугри которой указан номер двусвязного компонента, о котором идет речь в задании з) данной задачи). Точки сочленения, мосты и двусвязные компоненты можно найти при помощи поиска в глубину. Пусть С = ()г, Е ) — дерево поиска в глубину графа С. а) Докажите, что корень ф— точка сочленения графа С тогда и только тогда, когда он имеет как минимум два дочерних узла в С .

б) Пусть и — некорневая вершина С . Докажите, что и является точкой сочленения С тогда и только тогда, когда и имеет потомка в, такого что не существует обратного ребра от в или любого его потомка к истинному предку и. Часть Ч1. Алгоритмы для работы с графами Рис. 22.10. Точки сочленения, мосты и лвусвязные компоненты связного неориентированного графа в) Пусть 1ою [и] — минимальное значение среди Ы [и] и всех а [ю], где ю — вершины, для которых имеется обратное ребро (и, ю), где и— некоторый потомок и. Покажите, как можно вычислить 1ою [и] для всех вершин и е У за время 0 (Е).

г) Покажите, как найти все точки сочленения за время 0 (Е). д) Докажите, что ребро в С является мостом тогда и толью тогда, когда оно не принадлежит ни одному простому циклу С. е) Покажите, как найти все мосты за время О (Е). ж) Докажите, что двусвязные юмпоненты графа С составляют разби- ение множества всех ребер графа, не являющихся мостами. з) Разработайте алгоритм, который за время О (Е) помечает каждое ребро е графа С натуральным числом Ьсс [е], таким что Ьсс [е] = = Ьсс [е'] тогда и только тогда, когда е и е' находятся в одном и том же двусвязном компоненте.

22-3. Эйлеров цикл Эйлеров цикл (Еп1ег 1опг) сильно связного ориентированного графа С = = (К Е) представляет собой цикл, который проходит по всем ребрам С ровно по одному разу, хотя через вершины он может проходить по несюлько раз. а) Покажите, что в С имеется Эйлеров цикл тогда и только тогда, когда входящая степень каждой вершины равна ее исходящей степени. б) Разработайте алгоритм, который за время 0(Е) находит Эйлеров цикл графа С (если таковой цикл существует).

(Указание: обьединяйте циклы, у которых нет общих ребер.) 22-4. Достижимость , Пусть С = (КЕ) — ориентированный граф, в ютором каждая вер- шина и й У помечена уникальным целым числом Е(и) из множества Глава 22. Элементарные алгоритмы для работы с графами 643 (1, 2,..., (Щ. Для каждой вершины иЕУ рассмотрим множество В (и) = = [е е ч': и - ч) вершин, достижимых из и. Определим ш1п(и) как вершину в В(и), метка которой минимальна, т.е.

ш1п(и) — это такая вершина е, что Ь (с) = ппп [Ь (и): ш Е В (и)). Разработайте алгоритм, который за время О (У + Е) вычисляет пйп (и) для всех вершин и Е Ъ'. Заключительные замечания Превосходные руюводства по алгоритмам для работы с графами написаны Ивеном (Ечеп) [87] и Таржаном (Тат]ап) [292]. Поиск в ширину был открыт Муром (Мооге) [226] в контексте задачи поиска пути через лабиринт. Ли (Ьее) [198] независимо открыл тот же алгоритм при работе над разводкой печатных плат. Хопкрофт (Норсгой) и Таржан [154] указали на преимущества использования представления графов в виде списков смежности над матричным представлением для разреженных графов, и были первыми, кто оценил алгоритмическую важность поиска в глубину.

Характеристики

Список файлов книги