История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-12-21 | 778 |
5.00
из
|
Заказать работу |
|
|
Предположим заданным граф, числовые нагрузки (веса) дуг которого можно интерпретировать как их длины.
Выше уже отмечалось, что порождающих деревьев у графа может быть много. В рассматриваемом случае с каждым порождающим деревом естественно связать число, равное сумме длин всех его дуг. Ясно, что среди этих порождающих деревьев есть хотя бы одно, сумма длин всех дуг которого минимальна. Такое дерево называют минимальным порождающим деревом, minimum scanning tree, или минимальным остовом.
Начнем с рассмотрения двух примеров.
Пример 1. Имеется 7 городов А1, А2 , A3 , А4 , А5 , А6 , А7, которые нужно связать между собой наиболее дешевой сетью дорог, если известно, что стоимость сооружения участка дороги, соединяющей города Аi и Ак (i, к = 1,..., 7 ), пропорциональна ее длине (рис. 9).
Рис. 9. Исходная сеть
Замечание. Граф наиболее дешевой соединяющей сети непременно должен быть деревом. (Если бы это было не так, то в графе нашелся хотя бы один замкнутый путь. При удалении любого из ребер этого замкнутого пути стоимость сети уменьшилась бы, а города все еще оставались соединенными.) Тем самым число ребер искомого графа в предложенном примере должно быть равным 6.
Поиск решения можно начать с любого узла. Пусть это будет узел А1.
1-й шаг. Самая короткая дуга, выходящая из этого узла, — это дуга (А1, А2)длины 50. Соединим узлы А1 и А2 жирной линией, как показано на рис. 10а, и пометим узлы А1 и А2.
Рис. 10а
2-й шаг. Самой короткой дугой, выходящей из помеченных узлов А1 и А2, в еще непомеченные, является дуга (А2, А3).длины 40. Добавим ее к дереву, выделив жирной линией (рис. 10б)
Рис. 10б
3-й шаг. Узел А4 расположен к тройке А1, А2, А3 ближе всех других непомеченных узлов. Выделив дугу (А3, А4) длины 55, переведем этот узел в помеченные (рис. 10в) и пометим узел А4.
|
|
4-й шаг. Следующим узлом будет узел А6, расположенный к помеченной четверке А1, А2, А3, А4 ближе непомеченных узлов А 5 и А7. Выделим дугу (А3, А6)длины 75, соединяющую его с узлом А 3 (рис. 10в), и пометим узел А6.
5-й шаг. Узел А7, ближе узла А5 к пятерке помеченных узлов. Выделим дугу (А6, А7)длины 70, соединяющую его с ближайшим узлом A6, и пометим узел А7.
6-й шаг. Оставшийся непомеченным узел А5 соединим с узлом А7 дугой (А5, A7)наименьшей длины 45 и также пометим его.
Поведем итог: шесть выделенных дуг связывают все семь узлов заданной сети. Получающееся в результате минимальное порождающее дерево имеет суммарную длину 335
Предложенный способ хорошо работает и в случае, когда исходная сеть задана при помощи таблицы.
Пример 2. Пусть, например, нужно соединить города А, В, С, D и Е. Стоимости строительства дорог, соединяющих любые два города, известны
А | В | С | D | Е | |
А | — | ||||
В | — | ||||
С | — | ||||
D | — | ||||
Е | — |
Сеть дорог минимальной стоимости состоит из четырех, 5—1=4, дуг и строится так. Сначала выбирается самый дешевый участок дороги — ВС, соединяющий города В и С (его цена равна 6).
А | В | С | D | Е | |
А | — | ||||
В | — | ||||
С | - | ||||
D | - | ||||
Е | - |
Затем он удлиняется на самый дешевый из выходящих из городов В и С - СЕ (его цена равна 8).
А | В | С | D | Е | |
А | - | ||||
В | - | ||||
С | - | ||||
D | - | ||||
Е | - |
На третьем шаге вновь выбирается самый дешевый — это ЕА (его цена равна 7).
А | В | С | D | Е | |
А | - | ||||
В | - | ||||
С | - | ||||
D | - | ||||
£ | — |
Последний участок дороги выбираем так, чтобы не образовалось цикла: соединим для этого город D с ближайшим к нему городом В (его цена равна 9).
|
А | В | С | D | Е | |
А | - | ||||
В | - | ||||
С | - | ||||
D | — | ||||
Е | — |
Таким образом, минимальная стоимость строительства сети равна 6+ 8 + 7 + 9 = 30 (рис. 11).
Рис. 11.
Алгоритма Прима
Опишем алгоритм, предложенный Примом [8], считая, что число вершин заданного графа п > 2. Этот алгоритм приводит к искомому результату за п — 1 шаг.
1-й шаг. Пометим произвольную вершину графа. Из ребер инцедентных этой вершине, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, и которую входит это выбранное ребро. В результате две вершины графа оказываются помеченными.
Если других вершин в графе нет, то искомое порождающее дерево построено (обозначим его через Т)и поставленная задача решена. И противном случае потребуется новый шаг.
2-й шаг. Рассмотрим все ребра инцедентные помеченным вершинам, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результате выделенными оказываются два ребра графа, а помеченными уже три его вершины. Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребуется новый шаг.
3-й шаг. Рассмотрим все ребра инцедентным помеченным вершинам, за исключением тех, которые соединяют между собой уже помеченные вершины, выберем ребро наименьшей длины (если таких ребер несколько, выбираем любое из них) и пометим вершину, в которую входит это выбранное ребро. В результате выделенными оказываются три ребра графа, а помеченными уже четыре его вершины.
Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребуется новый шаг.
На каждом шаге и число выделенных ребер графа, и число помеченных вершин увеличиваются ровно на единицу. Тем самым, после п — 1-го шага количество выбранных ребер станет равным п — 1 и все п вершин графа окажутся помеченными.
Первый шаг можно начинать с ребра наименьшей длины. Его легко найти путем простого перебора всех ребер графа. Если таких ребер несколько, выберем любое из них и пометим концы выбранного ребра. В результате две вершины графа окажутся помеченными. Если других вершин в графе нет, то искомое порождающее дерево построено и поставленная задача решена. В противном случае потребуется новый шаг, совпадающий со 2-м шагом алгоритма, предложенного выше [9].
|
|
|
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!