1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 40
Текст из файла (страница 40)
Пусть 6= ()г, Е) — связный неориентированный граф и с — функция стоимости, заданная на его ребрах. Пусть ((1г! Т!) ()га, Те) ., (УА, Те)) — пРоизвольный остовный лес для 6, й ь1, и Т 0 Т! Лопустим,что е=(о, ш) — ребро наимень- гба шей стошиости в Š— Т, причем ой )г! и ш( Рь Тогда найдется вставное дерево для 6, содержащее Т(1 (е), стоимость которого не больше стоимости любого остовного дерева для 6, содержащего Т. Д о к а з а т е л ь с т в о. Допустим противное и обозначим через 5'= ()Г, Т') остовное дерево для 6, содержащее Т и не содержащее е, стоимость которого меньше стоимости любого остовного дерева для 6, содержащего Т 0 (е).
По лемме 5.1(б) добавление е к 5' образует цикл (см. рис. 5.1). Этот цикл должен содержать такое ребро е' = (о',ш'), отличное от е, что о' Е 'и', и ш' ( У!. По условию с (е)(с (е'). Рассмотрим граф 5, образованный' добавлением е к 5' и удалением е' из 5'. В 5 нет циклов, поскольку единственный цикл был разорван удалением ребра е'. Кроме того, все узлы в У все еще соединены, так как есть путь между о' и ш' в 5. Следовательно, 5 — остовное дерево для 6. Так как с (е)(с (е'), то стоимость дерева 5 не больше стоимости дерева 5'.
Но 5 содержит и Т, и е, что противоречит минимальности дерева 5'. С) Опишем алгоритм нахождения остовного дерева наименьшей стоимости для неориентированного графа 6= ()г, Е). Этот алгоритм по существу тот же, что и в примере 4.1. Он работает с набором У5 непересекающихся множеств узлов. Каждое множество (Р' из У5 представляет связное множество узлов, образующее остовное дерево в остовном лесу, представленном набором У5. Ребра выби- Рис. Зй. цикл в графе 6. 1Фв ан. остоннов диивво идимниьшгя стоимости Ьед!и Т-а; 2.
У5 — 8; 3. построить очередь с приоритетами !',1, содержащую все ребра из Е; 4. !ог о Е У г!о добавить (о) к У5; 5. ьтЬ!1е )У5(~ > 1 г!о Ьей(п 6. выбрать в 1~ ребро (о, ш) наименьшей стоимости; 7. удалить (о, пг) из Я; 8. И о и гв принадлежат различным множествам (Уг н Ф'а из УВ 1Ьеп Ьей!п заменить Ж', и !Р, на !Р„0%'а в У5; добавить (о, аг) к Т епд епд епд 9 10 Рис. З.2.
Алгоригм построения остовного дерева наименьшей стоимости. раются из Е в порядке возрастания стоимости. Ребра (о, пг) рассматриваются по очереди. Если о и гв принадлежат одному и тому же множеству из У5, то ребро (о, пг) исключается из рассмотрения. Если о и пг принадлежат разным множествам )Р, и Уйа (это означает, что )!гг и Чг, еще не соединены), то сливаем их в одно множество и добавляем (о, пг) к множеству Т ребер, входящих в окончательное остовиое дерево.
Здесь можно воспользоваться алгоритмом объединения непересекающихся множеств, описанным в разд. 4.7. Применив лемму 5.2 и проведя несложную индукцию по числу выбранных ребер, заключаем, что это ребро содержится по крайней мере в одном остовном дереве наименьшей стоимости для О. Алгоритм 5.1. Остовное дерево наименьшей стоимости (алгоритм Крус кала) Вход. Неориентированный граф б=(!', Е) с функцией стоимости с, заданной иа его ребрах.
Выход. Остовное дерево 5= (У, Т) наименьшей стоимости для 6. Метод. Программа приведена на рис. 5.2. П Пример 5.1. Рассмотрим неориентированиый граф на рис. 5.3. Перечислим его ребра в порядке возрастания их стоимостей: гл. а, ллгоиитмы ил гиаэлх Ребро Стоимость Ребро Стоимость ! 3 4 9 (6 !6 (64 64) (61 64) (61 64) (64, 61) (6, 64) (64 64) )7 20 23 23 28 36 (61 61) (64' 14) (64. 61) (64 61) (64. 64) (6„61) разумеется, на самом деле на шаге 3 алгоритма б,! ребра не сортируются, а хранятся в виде сортирующего дерева, 2-3-дерева или какой-нибудь другой приемлемой структуры данных, пока они не потребуются. Сортирующее дерево из разд. 3.4 фактически дает идеальный способ реализации очереди с приоритетами.
Повторное обращение в строке 6 с целью найти ребро наименьшей стоимости является основной операцией с Сортдеревом. Кроме того, число ребер, выбираемых в строке б для построения остовного дерева, часто меньше !)Е)!. В таких ситуациях мы экономим время, поскольку никогда не упорядочиваем Е полностью. Вначале каждое ребро находится в одноэлементном множестве, входящем в )75 и состоящем из самого этого ребра. Наименьшую стоимость имеет ребро (о„о,), так что оно добавляется к дереву и множества (6,) и (6,) в У5 сливаются.
ЗатЕМ раССМатрИВаЕтСя рЕбрО (644 Ов). ТаК КаК 6, И 64 ПрниадЛЕ- жат разным множествам из (75, добавляем (6„6,) к дереву и сли- ВаЕМ (64) И (64) ДаЛЕЕ дсбаВЛяЕМ (6„6,) И СЛИВаЕМ (6,) С (О„ 61). Добавляем также четвертое ребро (6„6,) и сливаем (6„6„6,) с (641 ов) ° Рис. 3,3. Неориеитироиаииыа граф с укаааииыми стоимостими его ребер. Ребро Действие Множества в Ю (связные подграфы) « О ) «О.). «О*) «О.) «О.) «О ) «О1» Оэ)» «Оз)» «Оа» Оа)» «Оа)» «Оа) «О1» Оз» Оэ)» «Оз» О4)» «Оа)» «Оа) «01 Оз Оа О4 Оэ) «Оа) «Оа) 1» 3» Оз» О4» Оа» Оз)» «04) «О1» ' ' 'э Оз) Рнс. 6.4. Последоввтельность шагов построения остовного дерева.
Затем рассматривается ребро (о„о,). Оба узла О, и о, принадлежат одному и тому же множеству «о„о„и„и„и,). Следовательно, из о, в О, идет путь из ребер, уже вошедших в остовное дерево, и потому (О„о,) ие добавляется. Вся последовательность шагов приведена на рис. 5.4. Остовное дерево, получающееся в резуль. тате, изображено на рнс. 5.5. П Теорема 5.1, Алгоритм 5.1 на«одигп остов«ос дераго наименьигей стоимости для связного гра(Ра О.
Если в цикле, олисанном стро«ами 5 — 10, рассматривается а' ребер, то затрачивается время 0(а!оде), где е=!!Е!!. Следовательно, алгоритм 5.1 занимает не более 0(е 1ойе) времени. Д о к а з а т е л ь с т в о. Корректность алгоритма вытекает непосредственно из леммы 5.2 и того факта, что строки 8 и 9 сохраняют узлы в том же самом множестве тогда и только тогда, когда (О1» 1) (Оз Оа) (и„о,) (Оз, Оэ) (О, Оз) (О4 Оэ) (Оаэ Оа) (О1, Оа) (О1 Оа) 4.1. ОстоВное деРИВО нАименьшей стоимости Добавить Добавить Добавить Добавить Отвергнуть Отвергнуть Добавить Отвергнуть Добавить Рнс. 6.6.
Остовное дерево нанненьшей стонноспь ГЛ. а. АЛГОРИТМЫ НА ГРАФАХ они принадлежат одному и тому же дереву остовного леса, представленного набором Ю. Для оценки времени допустим, что требуется д итераций цикла в строках 5 †!О. Нахождение ребра наименьшей стоимости в () (строка 6) занкмает 0(1ояе) шагов, если (1 реализуется очередью с приоритетами. Общее время нахождения всех множеств ЯГ, и (У„ содержащих и н ш (строка 8), и замены их на их объединение (строка 9) не превосходит 0(е0(е)) '), если применяется быстрый алгоритм объединения непересекающихся множеств.
Остальная часть цикла, очевидно, занимает постоянное время, не зависящее от размера О. Засылка начальных данных в () занимает время 0(е), а в УЗ вЂ” время 0(л), где и — число узлов в У. 0 $.1. МЕТОД ПОИСКА В ГЛУБИНУ Рассмотрим прохождение узлов неориентированного графа в следующем порядке.
Выбираем и "посещаем" некоторый начальный узел п. Затем выбираем произвольное ребро (о, ш), инцидентное о, и посещаем ш. Вообще пусть к — последний посещенный узел. Для продолжения процесса выбираем какое-нибудь не рассмотренное еще ребро (х, у), инцидентное х. Если узел у уже посещался, ищем другое новое ребро, ннцндентное х. Если у раньше не посещался, идем в у и заново начинаем поиск от узла у, Пройдя все пути, начинающиеся в узле у, возвращаемся в х, т, е, в тот узел, из которого впервые был достигнут увел у.
Затем продолжаем выбор нерассмотренных ребер, инцидентных узлу х, до тех пор, пока не будет исчерпан список этих ребер. Этот метод обхода узлов неориентированного графа называется поиском а глубину, поскольку процесс поиска идет в направлении вперед (вглубь) до тех пор, пока это возможно. Поиск в глубину можно также осуществлять и на ориентированном графе. Если граф ориентирован, то, находясь в узле х, мы выбираем ребра (х, у), только выходящие из х. Исследован все ребра, выходящие нз у, мы возвращаемся в х даже тогда, когда в и входят другие ребра, еще не рассмотренные. Если поиск в глубину осуществляется на связном неориентнрованном графе, то, как легко показать, посещается каждый узел и исследуется каждое ребро.
Если граф несвязен, то отыскивается его связная компонента. Закончив работу с ней, выбирают в качестве нового начального узла узел, который еще не посещался, и начинают новый поиск. Поиск в глубину на неориентированном графе 0 (У, Е) разбивает ребра, составляющие Е, на два множества Т и В. Ребро (о, ва) помещается в множество Т, если узел ш не посещался до того момента, когда мы, рассматривая ребро (п, ш), оказались в узле о. 1) Здесь Π— фуяяцяя, введеявая в равд. 4Л. — Прим. Ред.
Действие Ребро Множества в )гЗ (связные подграфы) (о» о ). (о.) (о.) (о.) (о.) (о ) (о о.) Ы. 1" .) (о.), (о.) (01 о о Ь (о оа) (оа) (ов) (От ое оэ оа~ от) (оа) Ы а' о оы от Ь (оа) (ом "э от) Рнс. 5.4. Последовательность шагов построения остовного дерева. Затем рассматривается ребро (о„о,). Оба узла о, и о, принадлежат одному и тому же множеству (о„о„о„о„о,). Следовательно, из о, в о, идет путь из ребер, уже вошедших в остовное дерево, и потому (о„о,) не добавляется. Вся последовательность шагов приведена на рис.
5.4. Остовное дерево, получающееся в результате, изображено на рис. 5.5. С) Теорема 5.1. Алгоритм 5.1 находит вставное дерево наименьшей стоимости для связного графа О. Если в цикле, описанном строками 5 — 1О, рассматривается д ребер, то затрачивается время 0(д!ояе), где е=(1Е1~. Следовательно, алгоритм 5.1 занимает не более 0(е!оде) времени. Д о к а з а т е л ь с т в о. Корректность алгоритма вытекает непосредственно из леммы 5.2 и того факта, что строки 8 и 9 сохраняют узлы в том же самом множестве тогда и только тогда, когда (о„о,) (оа оа) (о , от) (о„о,) (о„.) (оа от) (оа~ оь) (о„о,) (о„о,) аь остовнон двнаво нлимвньшни стоимости Добавить Добавить Добавить Добавить Отвергнуть Отвергнуть Добавить Отвергнуть Добавить Рнс. 5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
