Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 145
Текст из файла (страница 145)
22.5.3 Профессор считает, что алгоритм определения сильно связных компонентов можно упростить, если во втором поиске в глубину использовать исходный, а не транспонированный граф, и сканировать вершины в порядке возрастания времени завершения. Всегда ли этот более простой алгоритм будет давать корректные результаты? 22.5.4 Докажите, что для любого ориентированного графа С справедливо соотношение ((С~)~~~) = С~~~, т.е. что транспонироваиие графа компонентов для графа СТ дает тот же граф, что и граф компонентов графа С. 22.5.5 Разработайте алгоритм, который за время О($' + Е) находит граф компонентов ориентированного графа С = (1г, Е).
Убедитесь, что в полученном графе компонентов между двумя вершинами имеется не более одного ребра. 22.5.б Поясните, как для данного ориентированного графа С = (У, Е) создать другой граф С' = (1г, Е'), такой, что: (а) С' имеет те же сильно связные компоненты, что Часть КЬ Алгоритмы для работы с графами б58 и С; (б) С' имеет тот же граф компонентов, что и С; (в) Е' имеет минимально возможный размер. Разработайте быстрый алгоритм для вычисления С'. 22.5. 7 Ориентированный граф С = ($', Е) называется полусеязным (зеписоппес1ед), если для всех пар вершин и,и Е 1' мы имеем и» и или и и(или и то, и другое одновременно).
Разработайте эффективный алгоритм для определения, является ли данный граф С полусвязным. Докажите корректность разработанного алгоритма н проанализируйте время его работы. Задачи 22.1. Кчассификация ребер при поиске е ширину Лес поиска в глубину позволяет классифицировать ребра графа как ребра деревьев, обратные, прямые и перекрестные. Дерево поиска в ширину также можно использовать для аналогичной классификации ребер, достижимых из исходной вершины. ьь Докажите, что при поиске в ширину в неориентированном графе выполняются следующие свойства. 1.
Не существует прямых и обратных ребер. 2. Для каждого ребра дерева (и, и) имеем и. И = и. ь( + 1. 3. Для каждого перекрестного ребра (и, и) имеем и. ь1 = и. ь1 или и, ь) = и. ь1+1. б. Докажите, что при поиске в ширину в ориентированном графе выполняются следующие свойства. 1. Не существует прямых ребер. 2. Для каждого ребра дерева (и, и) имеем и.
г( = и. а' + 1. 3. Для каждого перекрестного ребра (и, и) имеем и. б < и. б + 1. 4. Для каждого обратного ребра (и, и) имеем 0 < и. ь1 < и. ь1. 22.2. Точки сочленения, мосты и Ьеусеязные каипоненты Пусть С = (К Е) является связным неориентированным графом. Точкой сочленения (агасси!айоп ро(п1) С называется вершина, удаление которой делает граф несвязным. Мостом (Ьйдйе) графа С называется ребро, удаление которого делает граф несвязным. Деусеязный компонент (Ысоппес1ед сошропеп1) графа С представляет собой максимальное множество ребер, такое что любые два ребра этого множества принадлежат общему простому циклу.
На рис. 22.10 проиллюстрированы приведенные определения. Точки сочленения, мосты и двусвязные компоненты можно найти с помощью поиска в глубину. Пусть С„= (ь', Е„)— дерево поиска в глубину графа С. б59 глава 22, Элеиетпарные алгоритмы для работы с графами Рис. 22ла. Точки сочленения, мосты и двусвязные вомпоненты связного неориентированного графа для задачи 22.2. Темным цветом на рисунке выделены точки сочленения (вершины) и мосты (ребра), а двусвязиые юмпоненты прелставялкп собой наборы ребер в заштрихованных областях (внутри юторых указаны номера Ьсс).
гь Докажите, что корень С вЂ” точка сочленения графа С тогда и только тогда, когда этот корень имеет как минимум два дочерних узла в С . 6. Пусть и — некорневая вершина С . Докажите, что и является точкой сочленения С тогда и только тогда, когда и имеет непосредственного потомка в, таюго, что не существует обратного ребра от л или любого его потомка к истинному предку и. а Пусть с. 1оге — минимальное значение среди с.
и' и всех гп. и', где гс — вершины, для которых имеется обратное ребро (н, гс), где и — некоторый потомок вершины п. Покажите, как вычислить п. (ого для всех вершин с б У за время О(Е). а Покажите, как найти все точки сочленения за время 0(Е). г).
Докажите, что ребро в С является мостом тогда и только тогда, когда оно не принадлежит ни одному простому циклу С. е. Покажите, как найти все мосты графа С за время 0(Е). згс Докажите, что двусвязные компоненты графа С составляют разбиение множе- ства всех ребер графа, не являющихся мостами. з. Разработайте алгоритм, который за время 0(Е) помечает каждое ребро е графа С натуральным числом е. бес, таким, что е. бес = е'. бес тогда и только тогда, когда е и е' находятся в одном и том же двусвязном юмпоненте. 22.3. Эйлеров цикл Эйлеров цикл (Еп!ег иют) сильно связного ориентированного графа С = (У, Е) представляет собой цикл, юторый проходит по всем ребрам С ровно по одному разу, хотя через вершины он может проходить по несюльку раз.
а Покажите, что в С имеется эйлеров цикл тогда и толью тогда, югда входящая степень каждой вершины равна ее исходящей степени: )п-с)е((гее(п) = опт-г1ейтее(п) для каждой вершины п б 1'. Часть 1б Алгоритмы дли работы с графами ббо б. Разработайте алгоритм, который за время 0(Е) находит эйлеров цикл графа С (если таковой цикл существует).
(Уиазаниег объединяйте циклы, у юторых нег общих ребер.) 22.4. Дослгижимосягь Пусть С = (У, Е) — ориентированный граф, в ютором каждая вершина и б У помечена уникальным целым числом Ци) из множества [1, 2,..., Щ]. Для каждой вершины и е У рассмотрим множество В(и) = (с е У: и» о) вершин, достижимых из и. Определим ш1п(и) как вершину в Л(и), метка которой минимальна, те. п21п(и) — это такая вершина с, что г (0) = пйп (2.(пг): нг Е В(и)]. Разработайте алгоритм, который за время 0(У + Е) вычисляет ш1п(и) для всех вершин и е У.
Заключительные замечания Превосходные руководства по алгоритмам для работы с графами написаны Ивеном (Ечеп) [102] и Таржаном (Таг]ап) [328]. Поиск в ширину был открыт Муром (Мооге) [258] в контексте задачи поиска пути через лабиринт. Ли (1.ее) [225] независимо открыл тот же алгоритм при работе над разводкой печатных плат. Хопкрофт (Норсгой) и Таржан [177] указали на преимущества использования представления графов в виде списков смежности над магричным представлением для разреженных графов и были первыми, кто оценил алгоритмическую важность поиска в глубину.
Поиск в глубину широко используется с конца 1950-х годов, в особенности в программах искусственного интеллекта. Таржан [325] разработал алгоритм поиска сильно связных компонентов за линейное время. Алгоритм из раздела 22.5 взят у Ахо (АЬо), Хопкрофта и Ульмана (1Л1шап) [6], которые ссылаются на неопубликованную работу С.Р. Косараю (Б.К. Козага]п) н работу Шарира (ЯЬапг) [312].
Габов (ОаЬотч) [118] разработал алгоритм для поиска сильно связных компонентов, который основан на сжатых циклах и использует два стека для обеспечения линейного времени работы. Кнут (Клпйл) [208]4 первым разработал алгоритм топологнчесюй сортировки за линейное время. Имеется русский перевод: Д. Киуг. Искусство ярограммироваиив, т.
Ь Осиовяые алгоритмы, 3-в ивд— Мг И Д. "Витяисз 2000 Глава 23. Минимальные остовные деревья При разработке электронных схем зачастую необходимо электрически соединить контакты нескольких компонентов. Для соединения множества из и контактов можно использовать некоторую компоновку из п — 1 проводов, калсдый из которых соединяет два контакта. Обычно желательно получить компоновку, которая использует минимальное количество провода. Эту задачу можно смоделировать с помощью связного неориентированного графа С = ()У,Е), где )г — множество контактов, Š— множество возможных соединений между парами контактов, и для каждого ребра (и, с) б Е задан вес в(и, с), определяющий стоимость (количество необходимого провода) соединения и и ю.
Мы хотим найти ациклическое подмножество Т С Е, которое соединяет все вершины и общий вес которого зс(Т) = у ш(и, тт) (и,и1ет минимален. Поскольку множество Т ациклическое и связывает все вершины, оно должно образовывать дерево, которое мы назовем ослаовным деревом (арапа(пй Псе) графа г .
Задача поиска дерева Т называется задачей поиска минимального вставного дерева (ш(п(шшп-зрашппй-нее ргоЫеш)'. На рис. 23.1 показан пример связного графа и его минимального остовного дерева. В этой главе мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева — алгоритмы Крускала (Кгцз1са1) и Прима (Рпш). Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О(Е 1к )г). При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до О(Е + $г 1к (У), что является весьма существенным ускорением, когда ~Ц гораздо меньше ~Е).
Оба эти алгоритма — жадные (см. главу 16). На каждом шаге алгоритма мы выбираем один из возможных вариантов. Жадная стратегия предполагает выбор варианта, наилучшего в данный момент. В общем случае такая стратегия не га- гно сути, термин "минимальное остовное дерево" означает "остовное дерево с минимальным весом". Мы не мини иизируем, например, коаичество ребер в т, поскольку все остовные деревья имеют ровно ٠— 1 ребер согласна теореме Бд бб2 Часть Нб Алгоритмы баа работы с графами Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
