В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 62
Текст из файла (страница 62)
г; = = (п,). Этот лес, очевидно, содержится в любом остове графа 6. Среди ребер, инцидентных оь выберем ребро минимального веса ирь и присоединим его к Т'. Согласно 1 теореме 75.1 существует минимальный остов, содержащий лес Т' = Т' О [иго» ], у которого компонента (У', Т,') содержит две вершины и1 из» и ребро иго», а осталь- 1 1' ные компоненты одновершинные. На следующем шаге будет выбрано и добавлено к Т' ребро минимального веса среди ребер, соединяющих(и„п» ) с Г6',(п„и» ) и т. д. Итак, стратегия построения минимального остова совершенно ясна: на каждом шаге присоединяется ребро, минимальное по весу среди ребер, соединяющих ужо построенный фрагмент минимального остова с вершинами, еще не включенными во фрагмент.
Нам остается только позаботиться об экономной реализации шагов этого процесса, С этой целью свяжем с каждой вершиной х ~ г'6 две метки а(х) и (»(х), смысл которых заключается в следующем. Пусть проделано )«шагов п (У» Тг) — фрагмент минимального остова, построенный к этому моменту, т. е. это компонента леса, к которой на предыдущих шагах присоединялись ребра минимального веса. Тогда а (х) = ш»п ю (х, п) = гз (х, и*), (» (х) = в«.
юегг ь Таким образом, к(х) — вес минимального по весу ребра, соединяющего вершину х с построенным фрагментом минимального остова, а р(х) — имя второй вершины этого ребра. Метки а(х) и р(х) позволяют быстро находить на каждом шаге ребро минимального веса. Кроме того, после присоединения очередной вершины и к фрагменту метки легко подкорректировать. Для этого достаточно сравнить «старое» значение а(х) с ю(и, х) н выбрать пз них меньшее в качестве «нового» значения а(х). В приводимом ниже описании алгоритма построения минимального остова помимо а(х) и р(х) использованы следующие обозначения: УТ, ЕТ вЂ” мпо»кества вершин и ребер строящегося фрагмента минимального остова; ӄ— окружение вершины х; ~С( = п. Граф С задан матрицей весов. Алгоритм »К» построения минимального остова.
1. Положить ЕТ:= И, »тТ:= (а), где а — любая вершипа из РС. Каждой вершине хая приписать метки а(х)= ш(х, а), если х ~в)у„и а(х)=, если хФд'„ р(х)= а. 2. (отьгскание вершины, «ближайшей» к фрагменту) . Выбрать вершину и* ~н Ь'С~~'(тТ согласно условию а(о*) = ппп а(и).
юпгот ут 3. (увеличение фрагмента). Пусть о' = р(и*). Изме- пить УТ и ЕТ, полагая УТ:= УТ 0 (о«), ЕТ;= := ЕТ 0 о'о". 4. Если ~(тТ~ = п, то конец. Ребра, находящиеся в множестве ЕТ, составляют минимальный остов. 5. Для каждой вершины и е= Аг,«П (УС'„'тТ) изменить метки следующим образом. Если а(о)) ш(о*, о), то а(о):= ш(о", и), р(о):= и*.
Если же а(о)» ш(и*, о), то метку вершины и не менять. Перейти к п. 2. У т в е р ж д е н и е 75.2. Алгоритм,оР» строит минимальный остов за время О(!С! ). (> Так как всякий раз к ЕТ добавляется ребро, один колец которого принадлежит Ь'Т, а другой нет, то граф Т =((тТ, ЕТ) на каждом шаге является деревом. После завершения работы алгоритма это дерево будет остовным, поскольку алгоритм прекращает работу только если УТ = УС. Докажем минимальность остова Т. Для этого достаточно доказать, что после Й-го (й = 1, и — 1) выполпения и. 3 алгоритма граф Х'=((тТ», ЕТ») содержится в некотором минимальном остове. Доказывать будем индукцией по й. При )г = 1 наше утверждение непосредственно следует из теоремы 75.1. Предположим, что опо справедливо для некоторого й) 1, т. е.
граф Т", построенный в результате й выполнений и. 3, содержится в некотором минимальном остове. Учитывая правило выбора ребра е для присоединения к Т", применим теорему 75.1. Получим, что граф Т»ы = Т" 0 е, построенный в результате (7«+ 1)-го выполнения п. 3, также содержится в некотором минимальном остове.
Выясним теперь быстродействие алгоритма. Однократное выполнение п. 2 требует времени не более О(!С~). Столько же времени достаточно для обновления меток в 22 в л, вмевичев и лр. 337 п. 5, а п. 3 и п. 4 выполняются эа время 0(1). Поскольку каждый нз пп. 2 — 5 выполняется п — 1 раз, то оценка трудоемкости алгоритма — 0 (! С ~ а) . 7 Пример 1. На рис.
75.1 иаображены граф С и последовательность Т' (д = 1, и — 1) фрагментов минимального остова, получающихся после каждой итерации алгоритма. Числа, приписанные ребрам графа С, означают г l а »1 l 4 7 д неа7 Г«,а7 б д а с а ! гс, а7 гд»7 с Да7 г' 'а ~а с| Рас. 75.1 веса этих ребер. Каждой вершине х, еще не вошедшей в Т', приписана пара чисел (с»(х), Р(х)), которыми она помечена в результате 4-го выполнения п.
5 алгоритма. Если граф 6 задан матрицей весов, то всякий алгоритм построения минимального остова в таком графе будет иметь сложность не менее чем 0((6(а), поскольку он, согласно замечанию 1, должен просматривать все элементы матрицы весов. Следовательно, в этой ситуации алгоритм Ф» имеет неуменьшаемую по порядку трудоемкость. Если же граф 6 задан списком ребер либо списками смежности и ~ЕС~ существенно меныпе чем ~6)~, то быстродействие алгоритма Ф» далеко от оптимального. ДРУгими словами, алгоРитм .4«'з неДостаточно эффективен в применении к «редкнм» графам, т. о.
к графам, слабо насыщенным ребрами. Рассмотрим еще один алгоритм построения минимального остова, ориентированный на работу именно с такими графами. Этот алгоритм (алгоритм с4»4), как и предыдущий, опирается на теорему 75 1, однако более полно нс- ЗЗЗ пользует предоставляемые ею возможности. Именно, если в алгоритме Фз ребро присоединяется всякий раз к одной и той же компоненте леса, то в алгоритме яг4 ребра присоединяются к кая|дой компоненте. Пусть Т = ((|ть Т|), ..., (|'„Тт)) — остовный лес графа С.
Назовем ребро аЬ минимальным по весу для компоненты (Уь Т|), 1 <(<Р, если а|я (ть Ь Ф )т, и |о(а, Ь) = ш(п и (х, у). Будем говорить, что М= катьват| = М(Т) — множество минимальных по весу ребер для леса Т, если для каждого ( = 1, р множество М содержит хотя бы одно минимальное по весу ребро для компоненты ((ть Т,) и, кроме того, М вЂ” минимальное по включению множество, обладающее этим свойством. Утверждение 75.3. Если М вЂ” множество минимальных но весу ребер для Т= ((Уь Т|), ..., ((тт, Тт)) то враф Т' = Т+ М не содержит циклов.
~> Доказываем от противного. Предположим, что Т содержит цикл Е, который не теряя общности будем считать простым. Пусть а|Ь|, азЬп ..., а,Ь,— ребра множества о' П М, выписанные в той последовательности, как они расположены в цикле о'. Этой последовательности соответствует последовательность компонент ( |та,, Та,), ((та,, Тд,), ..., (|та|, Тд|) леса Т, такая, что а, я ("ь, Ь, я я (т„,, а, я |т„, Ь,я Р~, ..., а, ен)ть,, Ь|я (ть .Выберем среди ребер а,Ь| (| = 1,() максимальное повесу. Пусть это будет ребро а|Ь|. Ясно, что а|Ь| является минимальным по весу ребром по крайней мере для одной из компонент ((ть, Ть ) или ()ть,, Ть,).
Не теряя общности считаем, что ребро а|Ь| — минимальное по весу для ((тд,, Ть,). Тогда и|(аь Ь|)= ю(а|, Ь|) н, следовательно, множество М||а|Ь| содержит хотя бы одно минимальное по весу ребро для каждой компоненты леса Т. Последнее противоречит минимальности множества М. З Перейдем теперь к изложению алгоритма .|з4. Этот алгоритм, так же, как и Фз, на первой итерации имеет дело с остовным лесом графа С, состоящим из и = |С| одновершинных компонент. Каждая итерация алгоритма состоит в следующем. Вначале строится множество М минимальных по весу ребер для леса Т, полученного в результате предыдущих итераций.
(Важно отметить, что сделать зто можно за один просмотр алементов множества ЕС.) Затем с помощью поиска в глубину выделяются 22Ф ззз связные компоненты графа Т' = Т+ М, который согласно утверждению 75.2 является лесом. После этого начинается следующая итерация с новым лесом Т', имеющим, очевидно, меньше компонент, чем Т. В приводимом ниже описании алгоритма с»»«используются следующие обозначения. Ребра графа 6 содержатся в списке Е, т. е. Е(1) — пара номеров концевых вершин 1-го ребра.
Список И' содержит веса ребер графа 6, т. е. И'(1) — вес 1-го ребра. Чтобы каждый раз строить множество минимальных по весу ребер для текущего леса за один просмотр списка Е, используются списки НМР, ВМР и КОМП: НМР(1) — номер минимального по весу ребра для 1-и компоненты текущего леса; ВМР(1) — вес этого ребра; КОМП(у) — номер компоненты текущего леса, содержащей вершину ). Пусть, далее, ЕТ вЂ” множество ребер текущего леса Т, а р — число его компонент; Е~ — множество минимальных по весу ребер для текущего леса Т.
Алгоритм .~Ф4 построения минимального остова. 1, ЕТ:= В, КОМП(1):= », ВМР(1):= для 1=1, л, р:= и. (Пп. 2 — 8 — построение множества Е~ минимальных по весу ребер для леса Т!. 2. й:= 1. 3. Пусть Е(й) = ищ»:= КОМП(и), 7:= КОМП(о) !» и 7 — номера компонент леса, содержащих вершины и н и соответственно). 4.
Если 1 чь у, то перейти к п. 5, иначе перейти к и. 7. 5. Коли ш(и, э)= И'(й)( ВМРЩ, то ВМР(7):= := ю(и, и), НМР(~'):= й. 8. Коли ш(и, и)= Иг(1с)~ ВМР(1), то ВМР(1):= = и(и, и), НМР(1):= й. 7. Если й =!Е6), то перейти к п. 8. Иначе й:= й+1 и перейти к п. 3. [К моменту выполнения и. 8 первые р элементов НМР содержат номера ребер, составляющих множество минимальных по весу ребер для Т.! 8. Просмотреть первые р элементов массива НМР и сформировать множество Е~ минимальных по весу ребер для леса Т. 9.
ЕТ:= ЕТ Б Е, 1ЕТ вЂ” множество ребер «нового» леса Т'!. 10. Выделить с помощью алгоритма поиска в глубину связные компоненты графа Т' Т + Е~ (обновлен список КОМП, получено новое значение р). 340 11. Если р = 1, то конец 1ЕТ вЂ” множество ребер минимального остова~. Иначе перейти к п. 2. Утверждение 75.4. Алгоритм Ф4 строит минимальный остов за время ОЦЕЯ 1оя!6!). ~> Нетрудно убедиться, что после каждого выполнения п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
