Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 148
Текст из файла (страница 148)
Покажите, что для любого минимального остовного дерева Т графа С можно указать способ сортировки ребер С, для которого алгоритм Крускала даст минимальное остовное дерево Т. гз.г.г Предположим, что граф С = (17, Е) представлен с помощью матрицы смежности. Разработайте для этого случая простую реализацию алгоритма Прима, время работы которой равно 0(Уз). гз.г.з Будет ли реализация алгоритма Прима с использованием фибоначчиевых пирамид асимптотически быстрее реализации с использованием бинарных пирамид для разреженного графа С = (Ъ', Е), для которого ~Е~ = В(Ъ')? А для плотного графа, в котором (Е! = В(17з)? Каким образом должны быть связаны ~Е! и ~Ъ'~, чтобы реализация с использованием фибоначчиевых пирамид была быстрее реализации с использованием бинарных пирамид? 22 Зви. 372в Часть гб Алгоритмы для работы с графами б74 23.2.4 Предположим, что все веса ребер графа представляют собой целые числа в диапазоне от 1 до ~Ц.
Насколько быстрым можно сделать алгоритм Крускала в этом случае? А в случае, когда вес каждого ребра представляет собой целое число в диапазоне от 1 до И' для некоторой константы И'? 23.2.3 Предположим, что все веса ребер графа представляют собой целые числа в диапазоне от 1 до Щ.
Насколько быстрым можно сделать алгоритм Прима в этом случае? А в случае, когда вес каждого ребра представляет собой целое число в диапазоне от 1 до И7 для некоторой константы Иг? 23.2.6 * Предположим, что веса ребер графа равномерно распределены на полуоткрытом интервале ~0, 1). Какой алгоритм — Крускала или Прима — будет работать быстрее в этом случае? 23.2. 7 * Предположим, что граф С имеет уже вычисленное минимальное остовное дерево.
Насколько быстро можно обновить минимальное остовное дерево при добавлении в С новой вершины и инцидентных ребер? Профессор предложил новый алгоритм декомпозиции для вычисления минимальных остовных деревьев, заключающийся в следующем. Для данного графа С = (17, Е) разбиваем множество вершин И на два подмножества $'1 и $'з, таких, что ~$71! и )17з! отличаются не более чем на 1. Пусть Е1 — множество ребер, инцидентных только с вершинами в Ры а Ез — множество ребер, инцидентных только с вершинами в 17з.
Рекурсивно решаем задачу поиска минимальных остовных деревьев в каждом из подграфов С1 = Я,Е1) н Сз = (~г, Ез) а затем выбираем среди ребер Е ребро с минимальным весом, пересекающее разрез Я, 17з), и используем его для объединения двух полученных минимальных остовных деревьев в одно. Либо докажите корректность описанного алгоритма поиска минимального остовного дерева, либо опровергните его, приведя контрпример, для которого алгоритм работает некорректно. Задачи 23.1. Второе минимальное остовное дерево Пусть С = (17, Е) — неориентированный связный граф с весовой функцией н7: Е -д Н; предположим, что (Е( > ~1г~ и что веса всех ребер различны. Определим второе минимальное остовное дерево следующим образом.
Пусть Т вЂ” множество всех остовных деревьев С и пусть Т' — минимальное 675 Глава 23. Мннанальные вставные деревьв остовное дерево С. Тогда вторым минимальным оетовным деревом (аесопбЬез~ пппппшп зрапшпя пее) будет такое остовное дерево Т, что ш(Т) пппт-ет-(т 1(ш(Т )). вь Покажите, что минимальное остовное дерево единственное, но вторых минимальных остоиных деревьев может быть несколько. б. Пусть Т вЂ” минимальное остовное дерево графа С.
Докажите, что граф С содержит ребра (и, в) Е Т и (т,у) ф Т, такие, что Т вЂ” ((и,е)) 0 ((е,у)) является вторым минимальным остовным деревом С. в. Пусть Т вЂ” остовное дерево С, и для любых двух вершин и, о б И обозначим через так(и, е] ребро максимального веса на единственном простом пути между и и о в Т. Разработайте алгоритм, который за время 0(172) для заданного Т вычисляет тат[и, о1 для всех и, е Е Ъ'. а Разработайте эффективный алгоритм вычисления второго минимального остовного дерева графа С.
23.2. Минилиьвьное вставное дерево разреженного графа Для очень разреженного связного графа С = (1',Е) можно добиться дальнейшего улучшения времени работы О(Е+ И (я И) алгоритма Прима с использованием фибоначчиевых пирамид путем предварительной обработки С в целях уменьшения количества его вершин перед применением алгоритма Прима. В частности, для каждой вершины и мы выбираем инцидеитное и ребро (и,о) с минимальным весом и помещаем это ребро в строящееся минимальное остовное дерево.
Затем мы выполняем сжатие всех выбранных ребер (см. раздел Б.4). Вместо того чтобы выполнять сжатие по одному ребру, мы сначала определяем множества вершин, которые объединяются в одну новую вершину. Затем мы создаем граф, который должен был бы получиться в результате объединения этих ребер по одному, но делаем зто путем "переименования" ребер соответственно множествам, в которых оказываются концы этих ребер.
При этом одинаково переименованными могут оказаться одновременно несколько ребер, и в таком случае в качестве результирующего рассматривается только одно ребро с весом, равным минимальному весу среди соответствующих исходных ребер. Изначально мы полагаем строящееся минимальное остовное дерево Т пустым и для каждого ребра (и, е) Е Е инициализируем атрибуты (и, о). ойд = (и, о) и (и, е). с = ш(и, о).
Атрибут обад используется для ссылки на ребро исходного графа, которое связано с данным ребром в сжатом графе. Атрибут с хранит вес ребра, и при сжатии его значение обновляется в соответствии с приведенной выше схемой выбора весов ребер. Процедура МБТ-Кипцсп получает в качестве входных параметров С и Т и возвращает сжатый граф С' с обновленными атрибутами обад' и с'. Процедура также переносит ребра из С в минимальное остовное дерево Т. бзб Часть КЕ Алгоритмы дла роботы с графами МЯТ-Кееп1се(С, Т) 1 Гог каждой вершины е Е С.
У 2 е.гпатк = ТАЕТЕ 3 МАКЕ-ЯЕТ(е) 4 1ог каждой вершины и Е С. У 5 Ы и. тпатК == ТАЕТЕ 6 выбрать вершину е Е С. Ай!и), такую, чтобы значение атрибута (и, е). с было минимальным 7 ЦХ!ОХ(и,е) 8 Т = Т 0 ((и, е). обад) 9 и.тпатй = е,тпат1с = Т1ШЕ 1О С~. У = (Р!Х0-БЕТ(е): е Е С.
У) 11 С'.Е = е 12 Гег каждого ребра (х,у) Е С. Е 13 и = Р1Х0-ЯЕТ(х) 14 е = Р1Х0-БЕТ(у) 15 1ь (и,е) ф С'.Е 16 С'. Е = С'. Е 1д 1(и, е) ) 17 (и, е). сад' = (х, у). сад 18 (и, е). с' = (х, у). с 19 е1яе 1т (х, у). с < (и, е).с' 20 (и,е).отзд' = (х,у).опд 21 (и, е). с' = (х, у). с 22 Построить списки смежности С'.
Аг(7' для С' 23 гетнгп С' и Т а Пусть Т вЂ” множество ребер, возвращаемое процедурой МБТ-Ке00се н пусть А — минимальное остовное дерево графа С', образованное вызовом МЯТ-Рк!м(С', с', т), где с' — атрибут веса для ребер из С'. Е, а т — произвольная вершина из С'. У. Докажите, что Т 1д ((х, у). опд'; (х, у) Е А) представляет собой минимальное остовное дерево графа С. б. Докажите, что ~С'. У! < Щ /2.
в. Покажите, как реализовать процедуру МБТ-Ке00се так, чтобы время ее работы составляло 0(Е). (Указание! воспользуйтесь простыми структурами данных.) г. Предположим, что мы й раз применяем процедуру МБТ-КЕ00сЕ, используя полученный при очередном вызове граф С' в качестве входных данных для следующего вызова и накапливаем ребра в Т.
Докажите, что общее время выполнения всех к вызовов составляет 0()сЕ). д. Предположим, что после 7с вызовов процедуры МБТ-КЕ011сЕ мы применяем алгоритм Прима, вызывая МБТ-РЕ1м(С', сг, т), где С' с атрибутом веса с' получен в результате последнего вызова процедуры МБТ-Ке00се, а т — произвольная вершина из С'. 1'. Покажите, как выбрать к, чтобы общее время Глава 73. Минимальные вставные деревья 677 работы составило 0(Е)к )к У). Докажите, что ваш выбор 6 минимизирует общее асимптотическое время работы.
е. Для каких значений 1Е( (выраженных через Щ) алгоритм Прима с предварительным сжатием эффективнее алгоритма Прима без сжатия? 23.3. Узкое остовнве дерево Назовем узким встовным деревом (Ьон!епеск зрапшпя ггее) Т неориентированного графа С остовное дерево С, в котором наибольший вес ребра минимален среди всех возможных остовных деревьев, и назовем этот вес значением узкого остовного дерева. в. Докажите, что минимальное остовное дерево является узким остовным деревом. Из части (а) следует, что поиск узкого остовного дерева не сложнее поиска минимального остовного дерева. В оставшейся части задачи мы покажем, что его можно найти за линейное время.
б. Разработайте алгоритм, который для данного графа С и целого числа 6 за линейное время определяет, превышает ли значение узкого остовного дерева число 6. в. Воспользуйтесь своим алгоритмом из п. (б) как подпрограммой в алгоритме решения задачи поиска узкого остовного дерева за линейное время. (Указание: можно воспользоваться подпрограммой сжатия множеств ребер, как в процедуре МБТ-йипцси, описанной в задаче 23.2.) 23.4. Альтернативные алгоритмы поиска минимальныл вставных деревьев В этой задаче мы приведем псевдокоды трех различных алгоритмов. Каждый из них принимает в качестве входных данных граф и возвращает множество ребер Т.
Для каждого из алгоритмов требуется доказать, что Т является минимальным остовным деревом графа, или доказать, что это не так. Кроме того, опишите эффективную реализацию каждого из алгоритмов, независимо от того, вычисляет он минимальное остовное дерево или нет. в. Маунти-МЯТ-А(С, ш) 1 Отсортировать ребра в невозрастающем порядке их весов и 2 Т=Е 3 1ог каждого ребра е в отсортированном порядке 4 !1' Т вЂ” (е) является связным графом 5 Т=Т вЂ” (е) б гегнгп Т Часть гт Алгориаьыы дла работы с графами б7в б.
МАувн-МБТ-В(С, и) 1 Т=И 2 Гвг каждого ребра е, взятого в произвольном порядке 3 !Г Т О (е] не имеет циклов 4 Т = ТО(е) 5 ге!пгп Т в. МАувн-МБТ-С(С, ш) 1 Т=й 2 !ог каждого ребра е, взятого в произвольном порядке 3 Т = ТО[е] 4 Н' Т имеет цикл с 5 Пусть е' — ребро максимального веса в с 6 Т = Т вЂ” [е'] 7 гезвгп Т Заключительные замечания В книге Таржана (Тат!ап) [328] содержится превосходный обзор задач, связанных с поиском минимальных остовных деревьев, и дополнительную информацию о них.
История данной задачи изложена Грехемом (ОгаЬаш) и Хеллом (Не!!) [150]. Таржан указывает, что впервые алгоритм для поиска минимальных остовных деревьев был описан в 1926 году в статье О. Борувки (О. Вогйтйа). Его алгоритм состоит в выполнении 0(18 17) итераций процедуры МБТ-Кнппсп, описанной в задаче 23.2. Алгоритм Крускала описан в [221] в 1956 году, а алгоритм, известный как алгоритм Прима, — в работе Прима (Рпш) [283], хотя до этого он был открыт В. Ярником (Ч. 1агп!и) в 1930 году. Причина, по которой жадные алгоритмы эффективно решают задачу поиска минимальных остовных деревьев, заключается в том, что множество лесов графа образует матроид (см.
раздел 16.4). Когда !Е~ = П(К 18 17), алгоритм Прима, реализованный с использованием фибоначчиевых пирамид, имеет время работы О(Е). Для более разреженных графов использование комбинации идей из алгоритма Прима, алгоритмов Крускала и Борувки вместе с применением сложных структур данных дало возможность Фред- ману (Ргетйпап) и Таржану [113] разработать алгоритм, время работы которого равно 0(Е 18" 17).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
