Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 146
Текст из файла (страница 146)
13Д. Минимальное остовное дерево славного графа. На ребрах указан их вес, а ребра минимального остовного дерева отдельно выделены цветом. Общий вес показанного дерева равен 37. Приведенное минимальное дерево не единственное: удалив ребро (Ь, с) и заменив его ребром (а, гг), мы получим другое остовное дерево с тем же весом 37. рантирует глобально оптимального решения задачи, однако для задачи поиска минимального остовного дерева можно доказать, что определенные жадные стратегии дают остовное дерево минимального веса. Хотя наспжщую главу можно читать независимо от главы 16, жадные алгоритмы, представленные Здесгь наглядно демонстрируют классическое применение изложенных в этой главе теоретических основ.
В разделе 23.1 описан "обобщенный" метод построения минимального остов- ного дерева, который наращивает остовное дерево по одному ребру. В разделе 23.2 приведены два варианта реализации обобщенного алгоритма. Первый алгоритм (Крускала) похож на алгоритм поиска связных компонентов из раздела 21.1.
Второй алгоритм (Прима) подобен алгоритму поиска кратчайшего пути Дейкстры (131)капа) из раздела 24.3. Поскольку дерево является разновидностью графа, чтобы быть точными, мы должны определять дерево не только через его ребра, но и через вершины. Хотя в этой главе деревья рассматриваются в основном через вершины, следует понимать, что вершины дерева Т вЂ” это то, что соединяют ребра дерева Т.
23.1. Выращивание минимапьного остовного дерева Предположим, что у нас есть связный неориентированный граф С = (К, Е) с весовой функцией зо: Е -+ К и мы хотим найти минимальное остовное дерево для С. В этой главе мы рассмотрим два алгоритма решения поставленной задачи, использующих, хотя и по-разному, один и тот же жадный подход. Эта жадная стратегия используется следующим обобщенным методом, который "выращивает" минимальное остовное дерево по одному ребру. Обобщенный метод работает с множеством ребер А, поддерживая следующий инвариант цикла.
Перед каждой очередной итерацией А представляет собой подмножество некоторого минимального остовного дерева. На каждом шаге алгоритма мы определяем ребро (и, и), которое можно добавить к А без нарушения этого инварианта, в том смысле, что А 1.) ((и, и)) также является подмножеством минимального остовного дерева. Мы назовем такое ребро ббЗ Глава гЗ. Минимальные вставные деревьв беэопаспмм (заГе ебйе) для А, поскольку его можно добавить к А, не опасаясь нарушить инвариант.
Овквк1с-МЗТ(С, ш) 1 А=6 2 твпйе А не образует остовного дерева 3 Найти ребро (и, и), безопасное для А 4 А = А 0 ((и,и)) 5 гегцгв А Инвариант цикла используется следующим образом. Инициализация. После выполнения строки 1 множество А тривиально удовлетворяет инварианту цикла. Сохранение. Цикл в строках 2-4 сохраняет инвариант путем добавления только безопасных ребер. Завершение. Все ребра, добавленные в А, находятся в минимальном остовном дереве, так что множество А, возвращаемое в строке 5, должно быть минимальным остовным деревом. Самое сложное, само собой разумеется, заключается в том, как именно найти безопасное ребро в строке 3.
Оно должно существовать, поскольку, когда выполняется строка 3, инвариант требует, чтобы существовало такое остовное дерево Т, что А С Т. Внугри тела цикла згпйе А должно быть истинным подмножеством Т, поэтому должно существовать ребро (и, и) Е Т, таюе что (и, и) ф А и (и,и)— безопасное для А ребро. В оставшейся части этого раздела мы приведем правило (теорема 23 1) для распознавания безопасных ребер. В следующем разделе описаны два алгоритма, которые используют это правило для эффекгивного поиска безопасных ребер.
Сначала нам потребуется несколью определений. Разрезом (спз) (Я, 1' — Я) неориентированного графа С = (г',Е) называется разбиение 1', что проиллюстрировано на рис. 23.2. Мы говорим, что ребро (и, и) Е Е пересекает (сгоззез) разрез (Я, Ъ' — Я), если один из его концов оказывается в множестве Я, а второй — в $' — Я. Разрез согласован (гезресг) с множеством ребер А, если ни одно ребро из А не пересекает разрез. Ребро, пересекающее разрез, является легким (!щЫ), если оно имеет минимальный вес среди всех ребер, пересекающих разрез. Заметим, что может бьггь несюлью легких ребер одновременно. В общем случае мы говорим, что ребро является легким ребрам, удовлетворяющим некоторому свойству, если оно имеет минимальный вес среди всех ребер, удовлетворяющих этому свойству. Правило для распознавания безопасных ребер дает следующая теорема.
Теорема 23.1 Пусп С = (К, Е) является связным неориентированным графом с действительной весовой функцией и, определенной на Е. Пусть А — подмножество Е, кото- бб5 Глава 25. йтннныальные останные дерееьл (чзтн Рнс. 2ЗЗ. Доказательство теоремы 22.К Черные вершины находятся в Я, а белые — в Р— Я. Показаны ребра в минимальном остовном дереве Т, но не ребра графа С. Ребра в А заштрихованы, а (н, о) представляет собой легкое ребро, пересекающее разрез (Я, и — Я). Ребро (х, Р) является ребром на единственном простом пути р от и до о в Т.
Чтобы получить минимальное осговное дерево Т', которое содержит (и, о), нужно удалить из Т ребро (х, Р) и добавить ребро (и, о). разбиение, ю(и, и) < ю(х, у). Следовательно, ю(Т ) = ш(Т) — ю(х, и) + ш(и,п) < ш(Т) . Однако Т вЂ” минимальное остовное дерево, так что ш(Т) < ш(Т'). Следовательно, Т' также должно быть минимальным остовным деревом.
Остается показать, что (и, н) действительно безопасное ребро для А. Мы имеем А С Т', поскольку А С Т и (х,у) ф А. Таким образом, А О ((и, и)) С Т' и, посколысу Т' — минимальное остовное дерево, ребро (и, п) безопасно для А. ° Теорема 23.1 помогает лучше понять, как метод Ончбк1с-МБТ работает со связным графом. В процессе работы алгоритма множество А всегда ациклнческое; в противном случае минимальное остовное дерево, включающее А, содерз жало бы цикл, что приводит к противоречию.
В любой момент выполнения алгоритма граф Сд = (1; А) представляет собой лес, а каждый из связных компонентов Сд является деревом. (Некоторые из деревьев могут содержать всего одну вершину, например, в случае, когда алгоритм начинает работу: множество А в зтот момент пустое, а лес содержит ~Ц деревьев, по одному для каждой вершины.) Кроме того, любое безопасное для А ребро (и, и) соединяет различные компоненты Сд, поскольку множество А О ((и, и)) должно быть ацнклическим. Цикл зтЫ$е в строках 2-4 процедуры Оймнк1с-МБТ выполняется ~Ц вЂ” 1 раз, он находит по одному из ~ (г ~ — 1 ребер минимального остовного дерева на каждой итерации.
Изначально, когда А = 9, в Сд имеется Щ деревьев, и каждая итерация уменьшает нх количество на единицу. Когда лес состоит только из одного дерева, алгоритм завершается. Два алгоритма, рассмотренные в разделе 23.2, используют следствие из теоре- мы 23.1. Часть РК Алгоритмы длл работы о графами ббб Следствие 23.2 Пусть С = (Ъ; Е) — связный неориентированный граф с действительной весовой функцией иг, определенной на Е. Пусть А — подмножество Е, которое входит в некоторое минимальное остовное дерево С, и пусть С = (Ъс, Ес) — связный компонент (дерево) в лесу СА = ($~, А).
Если (и, и) является легким ребром, соединяющим С с некоторым другим компонентом в СА, то ребро (и, и) безопасно для А. Доквзвтельсгяво. Разрез (Ъ~, У вЂ” Ъ~) согласован с А, а (и,и) — легкое ребро для данного разреза. Следовательно, ребро (и, и) безопасно для А. Упражнения 23.1.1 Пусть (и, и) — ребро минимального веса в связном графе С. Покажите, что (и, и) принадлежит некоторому минимальному остовному дереву С.
гз 1.2 Профессор утверждает, что верно следующее обращение теоремы 23А. Пусть С = (К Е) — связный неориентированный граф с действительной весовой функцией ю, определенной на Е. Пусть А — подмножество Е, входящее в некоторое минимальное остовное дерево С, (Я, У вЂ” Я) — произвольный разрез С, согласованный с А, и пусть (и, и) — безопасное для А ребро, пересекающее разрез (Я, У вЂ” Я).
Тогда (и, и) — легкое ребро для данного разреза. Приведите контр- пример, демонстрирующий некорректность профессорского обращения теоремы. 23.1.3 Покажите, что если ребро (и, и) содержится в некотором минимальном остовном дереве, то оно является легким ребром, пересекающим некоторый разрез графа. 23.1.б Приведите простой пример связного графа, такого, что множество ребер ((и, и): существует разрез (Я, Ъ' — Я), такой, что (и, и) является легким ребром, пересекающим (Я, У вЂ” Е) ) не образует минимального остовного дерева.
23.1.5 Пусть е — ребро с максимальным весом в некотором цикле связного графа С = (Г, Е). Докажите, что имеется минимальное остовное дерево графа С' = (У, Е— (е)), которое одновременно является минимальным остовным деревом С, те. что существует минимальное остовное дерево С, не включающее е. 23.1.6 Покажите, что граф имеет единственное минимальное остовное дерево, если для каждого разреза графа имеется единственное легкое ребро, пересекающее этот разрез.
Покажите с помощью контрпримера, что обратное утверждение не верно. гз.з,у Покажите, что если вес любого из ребер графа положителен, то любое подмножество ребер, объединяющее все вершины и имеющее минимальный общий вес, должно быть деревом. Приведите пример, показывающий, что это не так, если ребра могут иметь отрицательный вес. гз.1.8 Пусть Т вЂ” минимальное остовное дерево графа С и пусть 1, — отсортированный список весов ребер Т. Покажите, что для любого другого минимального остовного дерева Т' графа С отсортированный список весов ребер будет тем же. гз.1.у Пусть Т вЂ” минимальное остовное дерево графа С = (г', Е), а Ъ" — подмножество Г. Пусть Т' — подграф Т, порожденный $", а С' — подграф С, порожденный Г.
Покажите, что если Т' — связный граф, то он является минимальным остовным деревом С'. гз.1.10 Пусть даны граф С и минимальное остовное дерево Т. Предположим, что мы уменьшаем вес одного из ребер в Т. Покажите, что Т при этом останется минимальным остовным деревом С. Говоря более строго, пусть Т вЂ” минимальное остовное дерево С с весами ребер, заданными весовой функцией в. Выберем одно ребро (х, у) е Т и положительное число к и определим весовую функцию в' следующим образом: в (и, и), если (и, и) ф (х, у), в(и,и) = в(х, у) — к, если (и, и) = (х, у) . Покажите, что если веса ребер определяются функцией в', то Т остается мини- мальным остовным деревом С.
гз.1.11 * Пусть задан граф С и минимальное остовное дерево Т. Предположим, что мы уменьшаем вес одного из ребер, не входящих в Т. Разработайте алгоритм для поиска минимального остовного дерева модифицированного графа. 23.2. Алгоритмы Крускала и Прима Два описанных в этом разделе алгоритма следуют общей схеме поиска минимального остовного дерева. Каждый нз ннх использует свое правило для определения безопасных ребер в строке 3 процедуры бнчвк[с-МЯТ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
