Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 132
Текст из файла (страница 132)
Рассмотрим граф компонентов (Ст)ЗОО графа Ст. Если мы отобразим каждый сильно связный компонент, посещенный при втором поиске в глубину, на вершину (Ст)зоо, Часть Ч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] указали на преимущества использования представления графов в виде списков смежности над матричным представлением для разреженных графов, и были первыми, кто оценил алгоритмическую важность поиска в глубину.
Поиск в глубину широю используется с конца 1950-х годов, в особенности в программах искусственного интеллекта. Таржан [289] разработал алгоритм поиска сильно связных компонентов за линейное время. Алгоритм из раздела 22.5 взят у Ахо (АЬо), Хопкрофта и Ульмана (Ы1!шап) [6], которые ссылаются на неопубликованную работу Косараю (В.К. Козага]и) и работу Шарира (8Ьапг) [276]. Габов (ОаЬотч) [101] разработал алгоритм для поиска сильно связных компонентов, который основан на сжатых циклах и использует два стека для обеспечения линейного времени работы. Кнут (КпиГЬ) [182] первым разработал алгоритм топологической сортировки за линейное время.
ГЛАВА 23 Минимальные остовные деревья При разработке электронных схем зачастую необходимо электрически соединить контакты нескольких компонентов. Для соединения множества из и контактов мы можем использовать некоторую компоновку из п — 1 проводов, каждый из которых соединяет два контакта.
Обычно желательно получить компоновку, которая использует минимальное количество провода. Мы можем смоделировать эту задачу при помощи связного неориентированного графа С = (Ъ; Е), где $' — множество контактов, Š— множество возможных соединений между парами контактов, и для каждого ребра (и, и) й Е задан вес зл (и, и), определяющий стоимость (количество необходимого провода) соединения и и и.
Мы хотим найти ациклическое подмножество Т С Е, которое соединяет все вершины и чей общий вес ш(Т) = ~. 'ш(и,и) (н,е)еТ минимален. Поскольку множество Т ациклическое и связывает все вершины, оно должно образовывать дерево, которое мы назовем остовным деревом (зрапп)пд псе) графа С (иногда используется термин "покрывающее дерево"). Задачу поиска дерева Т мы назовем задачей лоиска минимального остовного дерева (пппппшпзрапп1пя-нее ргоЫеш)'. На рис. 23.1 показан пример связного графа и его минимального остовного дерева. На ребрах указан их вес, а ребра минимального остов- ного дерева отдельно выделены цветом. Общий вес показанного дерева равен 37.
'По сути, термин "минимальное остовное дерево" означает "остовное дерево с минимальным весом". Мы не минимизируем, например, количество ребер в Т, поскольку все остовные деревья имеют ровно ٠— 1 ребер согласно теореме Б.2. Глава 23. Минимальные остовные деревья 'ь), Рис. 23.1. Минимальное остовное дерево связного графа Приведенное дерево не единственное: удалив ребро (Ь, с) и заменив его ребром (а, Ь), мы получим другое остовное дерево с тем же весом 37.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
