1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 49
Текст из файла (страница 49)
Узел 3 является предком с наибольшим номером узлов 6 и 5 и узлов 8 и 4. Поэтому удаляем из С[31 состав ные ребра (3, (5)) и (1, (4)) н добавляем к б прямые ребра (3, 5) и (1, 4). Результат показан на рис. 5.33,6. Последующая часть поиска не приводит ни к каким изменениям. П Составные поперечные ребра можно представить 2-3-деревьями. Предлагаем в качестве упражнения формальное описание домина- торного алгоритма.
Если вы сможете найти подходящие структуры, вы освоили технику гл. 4 и 5. 246 УПРАЖНЕНИЯ упяажиания 5,1, Найдите остовное дерево наименьшей стоимости для графа на рис. 5.34, если все нарисованные ребра неориентированны. 5.2. Пусть Я=(У, Т) — остовное дерево наименьшей стоимости, построенное алгоритмом 5.1. Пусть с,<с,«...с„— стоимости ребер в Т. Пусть 3' — произвольное остовное дерево со стоимостями ребер 4<д,<...<д„.
Покажите, что с,<4 для 1<1<п. ""5.3. Чтобы за время 0(е) построить остовноедерево наименьшей стоимости для графа с и узлами и е ребрами в предположении, что е)~(п), где 1 — некоторая функция, которую вы должны найти, можно воспользоваться следующей стратегией. В различные моменты времени узлы будут группироваться в множества, связанные древесными ребрами, которые и тому времени уже найдены.
Все ребра, инцидентные одному или двум узлам из множества, будут храниться в приоритетной очереди для зтого множества. Вначале каждый узел находится в множестве, состоящем из него самого. Итерируемый шаг состоит в том, чтобы найти наименьшее множество Я и ребро с наименьшей стоимостью среди всех ребер, выходящих из 3; пусть это ребро ведет в множество Т. Затем добавляем его к остовному дереву и сливаем множества 3 и Т. Но если все множества имеют размер не меньше д(и), где д — другая функция, которую вам надо найти, то вместо этого образуем новый граф, где каждое множество представлено одним узлом.
Узлы нового графа, соответствующие множествам Я, и Ям полагаются смежными, если некоторый узел в Я, был смежен некоторому узлу в 5, в исходном графе. Стоимостью ребра, соединяющего 3, и 5, в новом графе, считается наименьшая из стоимостей ребер, соединяющих узел из 3, с узлом из о, в исходном графе. Далее этот алгоритм рекурсивно применяется к новому графу. Ваша задача — выбрать д(п) так, чтобы минимизировать )(а).
Рис. 5.34. Гл. а АлГОРитмы ИА ГРАФАХ Рис. 3.3б. 5.4. Постройте с помощью поиска в глубину остовный лес для неориентированного графа на рис. 5.35. Выбирайте в качестве исходного узла для построения очередного дерева любой узел. Найдите двусвязиые компоненты этого графа. 5.5. Постройте с помощью поиска в глубину остовный лес для ориентированного графа на рис. 5.34. Затем найдите сильно связные компоненты.
В.В. Найдите двусвязные компоненты графа на рис. 5.3В. 5.7. С помощью поиска в глубину разработайте эффективные алгоритмы, которые (а) разбивают неориентироваиный граф на его связные ко- поненты, (б) находят з неориентированном связном графе путь, прохо. дящий через каждое ребро точно один рав в каждом напраа6 ленин, Рис. б.зб. УПРАЖНЕНИЯ (в) проверяют, ацикличен ли ориентированный граф, (г) находят такой порядок узлов ациклического ориентированного графа, при котором о в, если из о ч ю ведет путь не. нулевой длины, (д) выясняют, можно ли так ориентировать ребра связного неориентированного графа, чтобы получить сильно связный ориентированный граф.
Указание: Покажите, что это можно сделать тогда и только тогда, когда удаление из О любого ребра оставляет граф связным. 5.8. Пусть О ° [У, Е) — мультиграф (т. е. ориентированный граф, у которого между двумя данными узлами может быть более одного ребра). Напишите алгоритм сложности ОЩЕя), который удаляет каждый узел о степени 2 (заменяя ребра (и, о) и (о, ю) ребром (и, э)) и уничтожает кратные ребра (заменяя их одним реб- ром).
Заметим, что замена кратных ребер одним ребром может при- вести к образованию узла степени 2, который затем следует уда- лить. Аналогично удаление узла степени 2 может привести к об- разованию кратных ребер, которые затем надо уничтожить. 5.9. Зйлеровым циклом в неориентированном графе называется путь, который начинается и кончается в одном и том же узле и проходит по каждому ребру точно один раз. Связный неориенти- рованный граф О имеет эйлеров цикл тогда и только тогда, когда степень каждого уала четна. Постройте алгоритм сложности 0(е) для нахождения эйлерова цикла в графе с я ребрами при условии, что такой цикл существует.
*5.10. Пусть О= (У, Е) — двусвязный неориентированный граф и (о, и) — его ребро. Пусть О' ((о, ю), ((о, ю))). Укажите способ выполнения в префиксном режиме последовательности операций НАЙТИ ПУТЬ (з, 1), где я — узел графа О', а (я, 1) — ребро графа О, но не О'. НАЙТИ ПУТЬ(з, 1) выполняется так: находим простой путь в С, начинающийся с ребра (я, 1) и кончающийся в некотором узле графа О', отличном от з, и добавляем узлы и ребра этого пути к О'. Время выполнения любой последовательности должно быть 0(!~Ей). 5.11.
Для ориентированного графа О на рис. 5.37 найдите (а) транзитивное замыкание, (б) длину кратчайшего пути между каждой парой узлов (стоимости ребер приведены на рис. 5.37; "5.12. Найдите замкнутое полукольцо из четырех элементов. "5.13. Транзитианая редукция ориентированного графа О= (У, Е) определяется как произвольный граф О'= (У, Е') с минимально возможным числом узлов, транзитивное замыкание которого сов- падает с транзитивным замыканием графа О. Покажите, что если граф О ацикличен, то его транзитивная редукция единственна.
Гл. а АлГОРитмы ИА ГРАФАХ Ряс. 5.37, **5.14. Покажите, что время Я(п) вычисления транзитивной редукции ациклического графа с а узлами имеет тот же порядок, что и время Т(п) вычисления транзитивного замыкания, если принять (разумное) допущение, что 81т (п))1Г (2а))41Г (а) и 8Т(п))Т(2л)) ~)4Т (л).
"5.15. Покажите, что время вычисления транзитивной редукции ациклического графа имеет тот же порядок, что и время вычисления транзитивной редукции произвольного графа, если принять те же допущения, что и в упр. 5.14. *5.16. Докажите то же, что и в упр. 5.15, для транзитивного замыкания. «5.17.
Пусть А будет (лХЛ)-матрицей над замкнутым полукольцом (О, 1). Не используя интерпретации на графах, докажите, что (а) А* = 1, + А + А' + ... + А", А В * А«А«ВС« Указание: Покажите, что упнджннния "5.18. Покажите, что алгоритм нахождения кратчайшего пути из равд. 5.8 работает, когда некоторые ребра имеют отрицательную стоимость, но никакой цикл не имеет отрицательной стоимости. Что случится, если у какого-нибудь цикла будет отрицательная стоимость? **5.19.
Покажите, что положительные и отрицательные вещественные числа с +оо и — оо не образуют замкнутого полукольца. Как в этом свете объяснить упр. 5.18? Указание: Какие свойства замкнутого полукольца фактически используются в алгоритме 5.5? 5.20. Примените алгоритм 5.6 для нахождения кратчайшего расстояния от узла о, в каждый узел о графа С на рис. 5.37. "5.21. Покажите, что задачу о нахождении кратчайшего пути из одного источника в случае неотрицательных стоимостей ребер для графа с е ребрами и л узлами можно решить за время 0(е !од л).
Указание: Используйте подходящую структуру данных, чтобы строки 5 н 8 алгоритма 5.6 можно было эффективно выполнить при е((л'. *"5.22. Покажите, что задачу о нахождении кратчайшего пути из одного источника в случае неотрицательных стоимостей ребер для графа с е ребрами и л узлами можно решить за время 0(ке+ +Йл'+ на) для любой фиксированной постоянной й. Ьей!п 5 — (оо) ! Р[о,Д О, 1ог о 6 У вЂ” (о,) г)о 0[о~ — 1(о„а); гнЬ1!е 5~У Йо Ьей!и выбрать такой увел ге~У вЂ” Я, что Р[аг) принимает наименьшее значение; Я -30 (пг); 1ог оЕУ, для которого 0[о~>0[ге)+1(ге, о) йо Ьей! п 0[о'1 0[ге'1+1(гв, о); 5 3 — (о) епг( епб епа Рнс. З.ЗЭ. Алгорнтн накождсння кратчайшего путя нз одного нсточннна.
2И Гл. а. АлГОРитмы ИА ГРАФАХ 1 2 3 4 5 О 7 8 9 10 0 0 8 9 10 0 — 2 0 9 10 0 — 4 — 3 0 !О 0 — 7 — 6 — 5 0 Рнс. 5.39. Стонмостн ребер лле Графа с б узламн. е5.23. Докажите, что алгоритм нахождения кратчайшего пути, приведенный на рис. 5.38, строит кратчайший путь из ие в каждый узел и произвольного графа, у которого могут быть ребра с отрицательными стоимостями, но циклов с отрицательными стоимостями нет. "5.24. Каков порядок времени работы алгоритма, приведенного на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
