Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Стягивающие деревья




Стягивающим (или остовным) деревом связного графа G называется произвольные его подграф G¢, содержащий все вершины графа G и являющийся деревом.

Существуют эффективные алгоритмы нахождения стягивающего дерева минимального веса в связном взвешенном графе.

В алгоритме Прима («ближайшего соседа») строится «разрастающееся» дерево, т.е. последовательность деревьев:

S1Ì S2Ì S3Ì…ÌSn,

где Si=<Vi, Ei> содержит i вершин (i=1, 2, …, n).

Этапы алгоритма «ближайшего соседа»:

1. Отмечаем произвольную вершину графа, с которой начинаем построение. Строим ребро наименьшего веса, инцидентное этой вершине в остовном дереве Т.

2. Ищем ребро минимально веса, одной из двух полученных вершин. В множество поиска не входит полученное ребро, так как оно исключается из исходного графа.

3. Продолжаем далее, разыскивая каждый раз ребро наименьшего веса, инцидентное построенным вершинам, не включая в круг поиска все ребра, их соединяющие.

4. Процесс продолжаем до тех пор, пока все вершины исходного графа не будут включены в Т, которое и будет минимальным остовным деревом.

Замечание: если исходный граф является ориентированным, то при реализации алгоритма необходимо учитывать направление дуг.

Рассмотрим пример решения задачи, используя алгоритм Прима.

Пример. Для графа, изображенного на рисунке 2.1, с помощью алгоритма Прима найти стягивающее дерево минимального веса.

 
х3
х2
х5
х4
х6
 
 
 
 
 
 
 
х1
 

 

 

Рис. 2.1

Решать з адачу будем пошагово, согласно алгоритму Прима.

Шаг 0. Выберем произвольную вершину, принадлежащую множеству вершин данного графа. Например, возьмем вершину х1 и включим ее в остовное дерево Т.

Шаг 1. Вершинам, инцидентным вершине х1 сопоставим пометки (ai, bi), где bi – наименьший вес ребра, соединяющего вершину хi c вершиной, уже включенной в дерево, т.е. на данном шаге вершиной х1, а ai – номер соответствующей вершины (х1). Остальным вершинам, не инцидентным вершине х1 присвоим пометку (0, ).

Полученные данные занесем в таблицу 2.1, первая строка которой соответствует шагу, вторая – множеству вершин V графа, не включенных в остовное дерево Т, следующие 5 строк для пометок вершин х1, а в последних двух строках будем записывать наименьший вес min (bi) и соответствующее ему ребро (ai, хi), вершину которого необходимо включить в дерево Т.

Вершине х1 инцидентны вершины х2, х3 и х6. Вершине х2 сопоставим пометку равную (х1, 4), так как х1 – единственная вершина, включенная в остовное дерево и соединенная с вершиной х2, а 4 – это вес ребра [ х1, х2 ]. Аналогично находим пометки для других вершин графа. Для вершины х3 пометка равна (х1, 4), а для вершины х6 - (х1, 5). Получаем что наименьший вес имеют ребра [ х1, х2 ] и [ х1, х3 ], т.е. min (bi)=b2= b3=4. Поэтому выбираем любое ребро, например [ х1, х2 ], и добавляем его в стягивающее дерево Т (табл. *.1).

Шаг 2. Каждой вершине из множества V={х3,…, х6} сопоставляем пометку, состоящую из наименьшего веса ребра, соединяющего вершину с какой-либо вершиной из множества VT={х1, х2}, и номера соответствующей вершины. Как видно из Таблицы *.1 на этом шаге в дерево Т добавилось ребро [ х2, х3 ] с весом min (bi)= b3=3.

Шаги 3 – 5 выполняем аналогичным образом.

Таблица 2.1
шаг          
Vгр 2,…, х6} 3,…, х6} 4, х5, х6} 4, х5} 4}
(a2, b2) 1, 4) - - - -
(a3, b3) 1, 4) (х2, 3) - - -
(a4, b4) (0, ∞) (0, ∞) 3, 7) 3, 7) 5, 2)
(a5, b5) (0, ∞) (0, ∞) (0, ∞) 5, 1) -
(a6, b6) 1, 5) 1, 5) 1, 5) - -
min (bi) b2 b3 b6 b5 b4
новое ребро х1 х2 x2 х3 х1 х6 x6 х5 х6 х5

В результате работы алгоритма получаем стягивающее дерево Т,изображенное на рисунке 2.2.

 
х3
х2
х5
х4
х6
 
 
 
 
х1

 

 

Рис. 2.2

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных