Алгоритмы - построение и анализ (1021735), страница 132
Текст из файла (страница 132)
Цикл в строках 2-4 процедуры Печно МБТ выполняется !Ъ'~ — 1 раз, так как должны быть найдены все !Ц вЂ” 1 ребер минимального остовного дерева. Изначально, когда А = В, в Сл имеется !T~ деревьев и каждая итерация уменьшает их количество на единицу. Когда лес содержит только одно дерево, алгоритм завершается. Два алгоритма, рассмотренные в разделе 23.2, используют следствие из теоремы 23.1. Следствие 23.2. Пусть С = (Ъ; Е) — связный неориентированный граф с действительной весовой функцией щ определенной на Е.
Пусть А — подмножество Е, которое входит в некоторое минимальное остовное дерево С, и пусть С = = (1с, Ес) — связный компонент (дерево) в лесу СА = (1; А). Если (и,и)— легкое ребро, соединяющее С с некоторым другим компонентом в Ся, то ребро (и,и) безопасно для А. Доказательство. Разрез (!'с, !' — Рс) согласован с А, и (и, и) — легкое ребро для данного разреза.
Следовательно, ребро (и, и) безопасно для А. И Упражнения 23.1-1. Пусть (и, и) — ребро минимального веса в графе С. Покажите, что (и, и) принадлежит некоторому минимальному остовному дереву С. 23.1-2. Профессор утверждает, что верно следующее обращение теоремы 23.!. Пусть С = (Р; Е) — связный неориентированный граф с действительной весовой функцией и, определенной на Е. Пусть А — подмножество Е, входящее в некоторое минимальное остовное дерево С, (5, Ъ" — Я)— произвольный разрез С, согласованный с А, и пусть (и,и) — безопасное для А ребро, пересекающее разрез (Я, 1' — Я).
Тогда (и, и) — легкое ребро для данного разреза. Приведите контрпример, демонстрирующий некорректность профессорского обращения теоремы. 23.1-3. Покажите, что если ребро (и, и) содержится в некотором минимальном остовном дереве, то оно является легким ребром, пересекающим некоторый разрез графа. 23.1-4. Рассмотрим множество всех ребер, каждый элемент которого является легким ребром для какого-то из возможных разрезов графа.
Приведите Часть Ч1. Алгоритмы для работы с графами простой пример, когда такое множество не образует минимального остов- ного дерева. 23.1-5. Пусть е — ребро с максимальным весом в некотором цикле связного графа С = (У, Е). Докажите, что имеется минимальное остовное дерево графа С' = (У, Š— (е)), которое одновременно является минимальным осговным деревом С, т.е. что существует минимальное остовное дерево С, не включающее е. 23.1-6.
Покажите, что граф имеет единственное минимальное остовное дере- во, если для каждого разреза графа имеется единственное легкое ребро, пересекающее этот разрез. Покажите при помощи коитрпримера, что обратное утверждение не верно. 23.1-7. Покажите, что если вес любого из ребер графа положителен, то любое подмножество ребер, обьединяющее все вершины и имеющее минималь- ный общий вес, должно быть деревом. Приведите пример, показываю- щий, что это не так, если ребра могут иметь отрицательный вес. 23.1-8. Пусть Т вЂ” минимальное остовное дерево графа С, и пусть Ь вЂ” отсор- тированный список весов ребер Т. Покажите, что для любого другого минимального остовного дерева Т' графа С отсортированный список весов ребер будет тем же. 23.1-9. Пусть Т вЂ” минимальное остовное дерево графа С = (У,Е)„а У'— подмножество У.
Пусть Т' — подграф Т, порожденный У', а С' — под- граф С, порожденный У'. Покажите, что если Т' — связный граф, то он является минимальным остовным деревом С'. что мы уменьшаем вес одного из ребер в Т. Покажите, что Т при этом останется минимальным остовным деревом С. Более строго, пусть Т— минимальное остовное дерево С с весами ребер, заданными весовой функцией ю.
Выберем одно ребро (х, у) е Т и положительное число й, и определим весовую функцию и' следующим образом: 1 то (и, о) если (и, о) Ф (х, у), и~'(и,о) = '(то(х,у) — Й если (и,о) = (х,у). Покажите, что если веса ребер определяются функцией ог', Т остается минимальным остовным деревом С. Пусть дан граф С и минимальное остовное дерево Т. Предположим, что мы уменьшаем вес одного из ребер, не входящих в Т. Разработайте ал- горитм для поиска минимального остовного дерева модифицированного графа. * 23.1-11. 23.1-10. Пусть дан граф С и минимальное остовное дерево Т.
Предположим, Глава 23. Минимальные остовные деревья 651 23.2 Алгоритмы Крускала и Прима Описанные в этом разделе алгоритмы следуют общей схеме поиска минимального остовного дерева. Каждый из них использует свое правило для определения безопасных ребер в строке 3 процедуры Оенен1с МБТ.
В алгоритме Крускала множество А является лесом. В А добавляются безопасные ребра, которые являются ребрами минимального веса, объединяющими два различных пэмпонеита. В алгоритме Прима множество А образует единое дерево. В А добавляются безопасные ребра, которые являются ребрами минимального веса, соединяющими дерево с вершиной вне дерева.
Алгоритм Крускала Алгоритм Крускала непосредственно основан на обобщенном алгоритме поиска минимального остовного дерева, приведенном в разделе 23.1. Он находит безопасное ребро для добавления в растущий лес путем поиска ребра (и, с) с минимальным весом среди всех ребер, соединяющих два дерева в лесу. Обозначим два дерева, соединяемые ребром (и, с), как С1 и Сз. Поскольку (и, с) должно быть легким ребром, соединяющим С1 с некоторым другим деревом, из следствия 23.2 вытекает, что (и, и) — безопасное для С1 ребро. Алгоритм Крускала является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом.
Наша реализация алгоритма Крускала напоминает алгоритм для вычисления связных компонентов в разделе 21.1. Она использует структуру для представления непересекающихся множеств. Каждое множество содержит вершины дерева в текущем лесу. Операция г1НР БЕт(и) возвращает представительный элемент множества, содержащего и. Таким образом, мы можем определить, принадлежат ли две вершины и и с одному и тому же дереву, проверяя равенство гп О БЕт(и) и г 1НП БЕт(п). Объединение деревьев выполняется при помощи процедуры 13н1он, МБТ КнцвкаЬ(С, тл) А 9 2 1ог Яля) каждой вершины с Е У[С] 3 Йо МАКЕ БЕТ(с) 4 Сортируем ребра из Е в неубывающем порядке их весов тл 5 1ог (Для) каждого (и, и) Е Е (в порядке возрастания веса) бо 1т г1хп Бет(и) Ф г1хп Бет(с) 7 1Ьеп А — АО1(и,с)) е УХЮХ(и, с) 9 гетпгп А Часть Ч1. Алгоритмы для работы с графами 652 б) е) л) ж) Рис. 23.4.
Выполнение алгоритма Крускала лля графа, приведенного на рис. 23.1. Заштрихованные ребра принадлежат растущему лесу А Алгоритм Крускала работает так, как показано на рис. 23.4. В строках 1-3 выполняется инициализация множества А пустым множеством и создается )Ц деревьев, каждое из которых содержит по одной вершине.
Ребра в Е в строке 4 сортируются согласно их весу в неубывающем порядке. Цикл 1ог в строках 5-8 проверяет для каждого ребра 1и, е), принадлежат ли его концы одному и тому же дереву. Если это так, то данное ребро не может быть добавлено к лесу без того, чтобы создать при этом цикл, поэтому в таком случае ребро отбрасывается. В противном случае, когда концы ребра принадлежат разным деревьям, в строке 7 ребро 1и, о) добавляется в множество А, и вершины двух деревьев объединяются в строке 8. Время работы алгоритма Крускала для графа С = 11; Е) зависит от реализации структуры данных для непересекающихся множеств. Мы будем считать, что лес непересекающихся множеств реализован так, как описано в разделе 21.3, с эв- Глава 23. Минимальные остовные деревья 653 м) ристиками объединения по рангу и сжатия пути, поскольку асимптотически это наиболее быстрая известная реализация.
Инициализация множества А в строке 1 занимает время 0 (1), а время, необходимое для сортировки множества в строке 4, равно 0 (Е18 Е) (стоимость )Ц операций Млкн Бит в цикле Гог в строках 2 — 3 мы учтем чуть позже). Цикл Гог в строках 5-8 выполняет 0(Е) операций р)н)э Бит и у)ч)Он над лесом непересекающихся множеств. Вместе с )'г') операциями Млкв БЕт эта работа требует времени О ИЪ'+ Е) а (Ъ')), где а — очень медленно растущая функция, определенная в разделе 21.4. Поскольку мы предполагаем, что С вЂ” связный граф, справедливо соотношение )Е! > ٠— 1, так что операции над непересекающимися множествами требуют 0 (Ео ($')) времени.
Кроме того, поскольку а()'м')) = 0(18$') = 0(18Е), общее время работы алгоритма Крускала равно 01Е!8 Е). Заметим, что )Е) < )Ъ')з, поэтому 18)Е~ = = 0 (18 У) и время работы алгоритма Крускала можно записать как 0 (Е 18 Ъ'). Алгоритм Прима Аналогично алгоритму Крускала, алгоритм Прима представляет собой частный случай обобщенного алгоритма поиска минимального остовного дерева из раздела 23.1. Алгоритм Прима очень похож на алгоритм Дейкстры для поиска кратчайшего пути в графе, который будет рассмотрен нами в разделе 24.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
