Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 135
Текст из файла (страница 135)
Время выполнения этой операции — 0 (18 1г). Таким образом, общее время работы алгоритма Прима составляет 0 (~'!8 1г + Е 18 ~") = О (Е 18 'г'), что асимптотически совпадает со временем работы рассмотренного ранее алгоритма Крускала. Однако асимптотическое время работы алгоритма Прима можно улучшить за счет применения фибоначчиевых пирамид. В главе 20 показано, что если Щ элементов организованы в фибоначчиеву пирамиду, то операцию Ехстлкст Мпч можно выполнить за амортизированное время О (1кЪ'), а операцию РескеАБе Кпу — за амортизированное время 0 (1).
Следовательно, при использовании фибоначчиевой пирамиды для реализации очереди с приоритетами Я общее время работы алгоритма Прима улучшается до 0 (Е+ У 18 1г). Упражнения 23.2-1. Алгоритм Крускала может возвращать разные остовные деревья для одного и того же входного графа О в зависимости от расположения ребер с одинаковым весом при сортировке. Покажите, что для любого минимального остовного дерева Т графа С можно указать способ сортировки 657 Глава 23. Минимальные остовные деревья ребер С, для которого алгоритм Крускала даст минимальное остовное дерево Т.
23.2-2. Предположим, что граф С = (К Е) представлен при помощи матрн- цы смежности. Разработайте простую реализацию алгоритма Прима для этого случая, время работы которой равно 0 (1'з). 23.2-3. Будет ли реализация алгоритма Прима с использованием фибоначчиевых пирамид асимптотически быстрее реализации с использованием бинарных пирамид для разреженного графа С = (1; Е), где ~Е~ = 0(1')? А для плотного графа, в ютором ~Е1 = 9 (Уз)? Каким образом должны быть связаны (Е~ и )Ц, чтобы реализация с использованием фибоначчиевых пирамид была быстрее реализации с использованием бинарных пирамид? 23.2-4.
Предположим, что все веса ребер графа представляют собой целые чис- ла в диапазоне от 1 до ~1'1 Насколько быстрым можно сделать алгоритм Крускала в этом случае? А в случае, югда вес каждого ребра представляет собой целое число в диапазоне от 1 до И' для некоторой константы И'? 23.2-5. Предположим, что вес каждого из ребер графа представляет собой це- лое число в диапазоне от 1 до ~Ц. Насколью быстрым можно сделать алгоритм Прима в этом случае? А в случае, когда вес любого ребра представляет собой целое число в диапазоне от 1 до И' для некоторой константы Иг? Предположим, что веса ребер графа равномерно распределены на по- * 23.2-6.
луоткрытом интервале [О, 1). Какой алгоритм — Крускала или Прима— будет работать быстрее в этом случае? Предположим, что граф С имеет уже вычисленное минимальное остов- * 23.2-7. ное дерево. Насколько быстро можно обновить минимальное остовное дерево при добавлении в С новой вершины и инцндентных ребер? Профессор предложил новый алгоритм декомпозиции для вычисления 23.2-8. минимальных остовных деревьев, заключающийся в следующем. Для данного графа С = ('1Г, Е) разбиваем множество вершин И на два подмножества Ъ'~ и Уз, таких что Я~ и Щ отличаются не более, чем на 1. Пусть Е1 — множество ребер, инцидентных только над вершинами в 1~м а Ез — множество ребер, инцидентных толью над вершинами в Из. Рекурсивно решаем задачу поиска минимальных остовных деревьев в каждом их подграфов С1 = Я,Ез) и Сз = Я,Ез), а затем выбираем среди ребер Е ребро с минимальным весом, пересекающее разрез Я, Уз), и используем его для обьединения двух полученных минимальных остовных деревьев в одно.
Докажите или опровергните корректность описанного алгоритма поиска минимального остовного дерева. Часть Ч1. Алгоритмы для работы с графами 658 Задачи 23-1. Второе минимальное остовное дерево С = (К Е) — неориентированный связный граф с весовой функцией ю: Š— В; предположим, что [Е[ > [Ц и что веса всех ребер различны. Определим второе минимальное остовное дерево следующим образом. Пусть Т вЂ” множество всех остовных деревьев С, и пусть Т' — минимальное остовное дерево С. Тогда вторым минимальным остовнмм деревам (зесопд-Ьезг пппппшп зраппш8 Згее) будет такое дерево Т, что ю (Т) = пппупет 1з ) (ш (Т )).
а) Покажите, что минимальное остовное дерево единственное, но вторых минимальных остовных деревьев может быть несколько. б) Пусть Т вЂ” минимальное остовное дерево С. Докажите, что существуют ребра (и, с) йТ и (х, у) ф Т, такие что Т вЂ” ((и, с) )0((х, у))— второе минимальное остовное дерево С. в) Пусть Т вЂ” остовное дерево С, и пусть для любых двух вершин и, с е У шах [и,е[ — ребро максимального веса на единственном пути между и и и в Т. Разработайте алгоритм, который за время О (Уз) для данного Т вычисляет шах [и, и] для всех и, с е У.
г) Разработайте эффективный алгоритм вычисления второго минимального остовного дерева С. 23-2. Минимальное остовное дерево разреженного графа Для очень разреженного связного графа С = (1;Е) можно добиться дальнейшего улучшения времени работы О (.Е + У 18 У) алгоритма Прима с использованием фибоначчиевых пирамид путем предварительной обработки С в целях уменьшения количества его вершин перед применением алгоритма Прима. В частности, для каждой вершины и мы выбираем инцидентное и ребро (и, о) с минимальным весом и помещаем это ребро в строящееся минимальное остовное дерево. Затем мы выполняем сжатие по всем выбранным ребрам (см.
раздел Б.4). Вместо того чтобы проводить сжатие по одному ребру, мы сначала определяем множества вершин, которые объединяются в одну новую вершину. Затем мы создаем граф, который должен был бы получиться в результате объединения этих ребер по одному, но делаем это путем "переименования" ребер соответственно множествам, в которых оказываются концы этих ребер.
При этом одинаково переименованными могут оказаться одновременно несколько ребер, и в таком случае в качестве результирующего рассматривается только одно ребро с весом, равным минимальному весу среди соответствующих исходных ребер. Глава 23. Минимальные остовные деревья 659 Изначально мы полагаем строящееся минимальное остовное дерево Т пустым, и для каждого ребра (и, и) е Е выполняем присвоения ог$9 [и, и] = = (и, и) и с [и, и] = ш(и, ю). Атрибут ог$д используется для ссылки на исходное ребро графа, которое связано с данным ребром в сжатом графе. Атрибут с хранит вес ребра, и при сжатии его значение обновляется в соответствии с приведенной выше схемой выбора весов ребер. Процедура МБТ Кю11се получает в качестве входных параметров С, сг$д, с и Т, и возвращает сжатый граф С' и обновленные атрибуты ог$д' и с' для графа С'. Процедура также переносит ребра из С в минимальное остовное дерево Т.
МБТ КЕ011СЕ(С, ог$9, с,Т) 1 1ог (Для) каждого и Е 'г'[С] 2 Йо татки] ЕА1 зе 3 МАКЕ БЕТ(и) 4 $аг (Для) каждого и Е ЦС] 5 $$о $Т тагй[и] = ТА1ле 6 $$1еп Выбираем ю Е А4[и] с минимальным с[и, и] 7 П1ч10х(и, ю) 8 Т - Т11(ог$9[и, ю]) 9 таге] +- татЬ[и] - ТК1/Е 1О ЦС'] +- (Р1х$1 Бет(и): и е У[С]) 11 Е[С'] — О 12 $ог (Для) каждого (х, у) Е Е[С] 13 $$о и ~ — Р1Н13 БЕТ(х) 14 — Р1н13 Бет(у) $$' (и, и) ЯЕ[С'] 16 $$$еп Е[С] "- Е[С] ~! ((и'")) 17 огни, ю] — огзд[х У] 18 с'[и,и] с[х у] !9 е!ве !1 с[х,у] < с'[и и] 20 $$$еп ог$9'[и, и] — ог$9[х у] 21 с'[и,и] - с[х У] 22 Строим списки смежности Аг$3 $ог С' 23 гегпгп С', ог$9', с' и Т а) Пусть Т вЂ” множество ребер, возвращаемое процедурой МБТ Кео11се, и пусть А — минимальное остовное дерево графа С', образованное вызовом МБТ Ри1м(С', с', г), где г — произвольная вершина из $г [С'].
Докажите, что Т 13 (ог$д' [х, у]: (х, у) Е А) представляет собой минимальное остовное дерево графа С. б) Докажите, что ['г" [С'][ < [г'[/2. 660 Часть Ч!. Алгоритмы для работы с графами в) Покажите, как реализовать процедуру МВТ Кнппсн так, чтобы время ее работы составляло О (Е). (Указание: воспользуйтесь простыми структурами данных.) г) Предположим, мы 1с раз применяем процедуру МБТ Кюпсн, используя полученные при очередном вызове С', ог)д' и с' в качестве входных данных для следующего вызова и накапливаем ребра в Т. Покажите, что общее время выполнения всех к вызовов составляет О ()с Е). д) Предположим, что после к вызовов процедуры МБТ йюпсн мы применяем алгоритм Прима МБТ Рнм1С', с', г), где С' и с' получены в результате последнего вызова процедуры МЯТ Кюг!сн, а г— произвольная вершина из У [С'].
Покажите, как выбрать к, чтобы общее время работы составило 01Е1к1яУ). Докажите, что ваш выбор )с минимизирует общее асимптотическое время работы. е) Для каких значений !Е~ (выраженных через !У!) алгоритм Прима с предварительным сжатием эффективнее алгоритма Прима без сжатия? 23-3. Узкое остовное дерево Назовем узким оставиым деревом (Ьоп!епеск зрапп!пя !гее) Т неориентированного графа С остовное дерево С, в котором наибольший вес ребра минимален среди всех возможных остовных деревьев, и этот вес называется значением узкого остовного дерева.
а) Докажите, что минимальное остовное дерево является узким остовным деревом. Из части а) следует, что поиск узкого остовного дерева не сложнее поиска минимального остовного дерева. В оставшейся части задачи мы покажем, что его можно найти за линейное время. б) Разработайте алгоритм, который для данного графа С и целого числа Ь за линейное время определяет, превышает ли значение узкого остовного дерева число Ь или нет. в) Воспользуйтесь вашим алгоритмом из части б) как подпрограммой в алгоритме решения задачи поиска узкого остовного дерева за линейное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
