Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 133
Текст из файла (страница 133)
В этой главе мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева — алгоритм Крускала (КпЫса1) и Прима (Рптп). Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О (Е 1к Ъ'). При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до О (Е + Ъ' 1к Ъ'), что является весьма существенным ускорением при ~Ц << )Е!. Оба эти алгоритма — жадные (см. главу 16).
На каждом шаге алгоритма мы выбираем один из возможных вариантов. Жадная стратегия предполагает выбор варианта, наилучшего в данный момент. В общем случае такая стратегия не гарантирует глобально оптимального решения задачи, однако для задачи поиска минимального остовного дерева можно доказать, что определенные жадные стратегии дают нам остовное дерево минимального веса. Хотя настоящую главу можно читать независимо от главы 1б, жадные алгоритмы, представленные здесь, наглядно демонстрируют классическое применение изложенных в этой главе теоретических основ.
В разделе 23.1 описана общая схема построения минимального остовного дерева, которая наращивает остовное дерево по одному ребру. В разделе 23.2 приведены два пути реализации обобщенного алгоритма. Первый алгоритм (Крускала) похож на алгоритм поиска связных компонентов из раздела 21.1. Второй алгоритм (Прима) подобен алгоритму поиска кратчайшего пути Дейкстры (131)касса) из раздела 24.3.
23.1 Построение минимального остовного дерева Предположим, что у нас есть связный неориентированный граф С = (г', Е) с весовой функцией ю: Š— ~ К, и мы хотим найти минимальное остовное дерево Часть Ч1. Алгоритмы для работы с графами для С.
В этой главе мы рассмотрим два жадных алгоритма решения поставленной задачи. Оба рассматриваемых алгоритма имеют общую схему, согласно которой минимальное остовное дерево растет путем добавления к нему ребер по одному. Алгоритм работает с множеством ребер А, и инвариант цикла алгоритма выглядит следующим образом: Перед каждой очередной итерацией А представляет собой подмноже- ство некоторого минимального остовного дерева. На каждом шаге алгоритма мы определяем ребро (и, о), юторое можно добавить к А без нарушения этого инварианта, в том смысле, что А 0 Г(и, о)) также является подмножеством минимального остовного дерева.
Мы назовем такое ребро безопасным (за1е ебйе) для А, поскольку его можно добавить к А, не опасаясь нарушить инвариант. Оегчеис МБТ(С, и) А И 2 ттЫ1е А не является минимальным остовным деревом 3 до Найти безопасное для А ребро (и, с) 4 А — АО~(и,с)) 5 гетиги А Мы используем инвариант цикла следующим образом. Инициализация. После выполнения строки 1 множество А тривиально удовлетворяет инварианту цикла. Сохранение.
Цикл в строках 2-4 сохраняет инвариант путем добавления только безопасных ребер. Завершение. Все ребра, добавленные в А, находятся в минимальном остовном дереве, так что множество А, возвращаемое в строке 5, должно быть минимальным остовным деревом. Самое важное, само собой разумеется, заключается в том, как именно найти безопасное ребро в строке 3.
Оно должно существовать, посюльку когда выполняется строка 3, инвариант требует, чтобы существовало такое остовное дерево Т, что А С Т. Внутри тела цикла ттЫ1е А должно быть истинным подмножеством Т, поэтому должно существовать ребро (и, с) Е Т, такое что (и, с) ф А и (и, о)— безопасное для А ребро. В оставшейся части этого раздела мы приведем правило (теорема 23.1) для распознавания безопасных ребер. В следующем разделе описаны два алгоритма, которые используют это правило для эффективного поиска безопасных ребер.
Глава 23. Минимальные остовные деревья 647 15 „'г-5 а) Рис. 23.2. Два варианта представления разреза (5, У вЂ” Я) графа, приведенного на рнс. 23.1 Начнем с определений. Разрпом (сит) (Я, Ъ' — Я) неориентированного графа С = (К Е) называется разбиение У, что проиллюстрировано на рис. 23.2 (вершины в множестве Я окрашены в черный цвет, а в множестве Ъ' — Я вЂ” в белый). Мы говорим, что ребро (та, о) Е Е пересекаева (сгоззез) разрез (5, У вЂ” Я), если один из его концов оказывается в множестве Я, а второй — в У вЂ” Я. Разрез согласован (гезрест) с множеством А по ребрам, если ни одно ребро из А не пересекает разрез. Ребро, пересекающее разрез, является легким (йй(тт), если оно имеет минимальный вес среди всех ребер, пересекающих разрез.
Заметим, что может быть несколько легких ребер одновременно. В общем случае мы говорим, что ребро является легким ребром, удовлетворяющим некоторому свойству, если оно имеет минимальный вес среди всех ребер, удовлетворяющих данному свойству. Наше правило для распознавания безопасных ребер дает следующая теорема. Теорема 23.1.
Пусть 0 = (К Е) — связный неориентированный граф с действительной весовой функцией и, определенной на Е. Пусть А — подмножество Е, которое входит в некоторое минимальное остовное дерево С, (Я, У вЂ” Я) — разрез С, согласованный с А по ребрам, а (и, о) — легкое ребро, пересекающее разрез (Я, У вЂ” Я).
Тогда ребро (та, о) является безопасным для А. Доказалаельстао. Пусть Т вЂ” минимальное остовное дерево, которое включает А, и предположим, что Т не содержит ребро (та, и), поскольку в противном случае теорема доказана. Мы построим другое минимальное остовное дерево Т', Часть Ч1. Алгоритмы для работы с графами 648 Рис. 23.3. Иллюстрация к доказатель- ству теоремы 23.1 которое включает А О ((и, и)), путем использования метода вырезания и вставки, показывая таким образом, что ребро (и, и) являе~ся безопасным для А. Ребро (и, и) образует цикл с ребрами на пути р от и к и в Т, как показано на рис. 23.3. Поскольку и и и находятся на разных сторонах разреза (Я, У вЂ” Я), на пути р имеется как минимум одно ребро из Т, которое пересекает разрез.
Пусть таким ребром является ребро (х, у). Ребро (х, у) не входит в А, поскольку разрез согласован с А по ребрам. Так как (х, у) является единственным путем от и к и в Т, его удаление разбивает Т на два компонента. Добавление (и, и) восстанавливает разбиение, образуя новое остовное дерево Т' = Т вЂ” ((х, у)) 0 ((и, и)). Теперь мы покажем, что Т' — минимальное остовное дерево. Поскольку (и, и) — легкое ребро, пересекающее разбиение (Я, У вЂ” Я), и (х, у) также пересекает это разбиение, ю (и, и) < ю (х, у). Следовательно, ю (Т') = ю(Т) — ю(х,у) + ю(и,и) < ю(Т).
Однако Т вЂ” минимальное остовное дерево, так что ю (Т) < ю (Т'). Следовательно, Т' также должно быть минимальным остовным деревом. Остается показать, что (и, и) действительно безопасное ребро для А. Мы имеем А С Т', поскольку А С Т и (х, у) ф А. Таким образом„А 0 ((и, и)) С Т' и, поскольку Т' — минимальное остовное дерево, ребро (и, и) безопасно для А.д Теорема 23.1 помогает нам лучше понять„как работает процедура Оечнк)с МБТ. В процессе работы алгоритма множество А всегда ацикпическое; в противном случае минимальное остовное дерево, включающее А, содержало бы цикл, что приводит к противоречию. В любой момент выполнения алгоритма граф Сл = = (Ъ; Е) представляет собой лес и каждый из связных компонентов С,~ является Глава 23. Минимальные остовные деревья 649 деревом.
(Некоторые из деревьев могут содержать всего одну вершину, например, в случае, когда алгоритм начинает работу: множество А в этот момент пустое, а лес содержит Щ деревьев, по одному для каждой вершины.) Кроме того, любое безопасное для А ребро (и, и) соединяет различные компоненты СА, поскольку множество А О ((и, и) ) должно быть ациклическим. Цикл в строках 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. Пусть Т вЂ” минимальное остовное дерево графа С, и пусть Ь вЂ” отсор- тированный список весов ребер Т. Покажите, что для любого другого минимального остовного дерева Т' графа С отсортированный список весов ребер будет тем же.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
