Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Каркас. Алгоритм Прима

Читайте также:
  1. RSVP алгоритммен тарату жүйесіне QoS-көрсеткішінің табу әдістемесі
  2. Алгоритм
  3. Алгоритм 1. Сила Мистического Сознания.
  4. Алгоритм 2. Состояние ДИВО (Динамической Воли).
  5. Алгоритм 3. Состояние Имагинатора.
  6. Алгоритм 4. Кристаллизация Я.
  7. Алгоритм введения и изменения заряда точки привязки

Остовное дерево или каркас графа - подграф графа, который:

1) содержит все вершины графа,

2) является деревом.

Задача. Найти минимальное остовное дерево в неориентированном взвешенном графе G.

Алгоритм (метод Прима):

1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G2 графа G. Положим i:=2.

2) Если i=n(G), то задача решена и Gi – искомое минимальное остовное дерево графа G. Иначе переходим к шагу 3.

3) Строим граф Gi+1. Для этого добавим к графу Gi новое ребро минимальной длины из оставшихся, которое инцидентно какой-либо вершине графа Gi и одновременно вершине, не содержащейся в Gi. Вместе с этим ребром включаем в Gi+1 и эту инцидентную ему вершину. Присваиваем i:=i+1 и переходим к шагу 2.

 

Пример.

Найдем минимальное остовное дерево в неориентированном взвешенном графе, изображенном на рис.

 

Обозначим ребро, соединяющее вершины vi и vj через xij.

 

Для удобства использования приведенного выше алгоритма решения поставленной задачи, составим матрицу длин ребер. В рассматриваемом графе количество вершин n=8, следовательно, матрица длин ребер графа G будет иметь размерность 8×8 и выглядеть следующим образом:

 

Согласно приведенному выше алгоритму, выбираем ребро минимальной длины (c47=1) и вместе с инцидентными ему двумя вершинами относим к графу G2. Таким образом, .

Длина дерева G2 будет равна l(G2)=c47=1. Поскольку , продолжаем работу алгоритма. По четвертой и седьмой строкам ищем минимальное число (за исключением использованной единицы) − ребро минимальной длины, инцидентное либо вершине v4, либо v7. Выбираем ребро x46 с длиной c46=3 и вместе с вершиной v6 добавляем к графу G2, обозначая его теперь как G3:

, при этом l(G3)=c47+c46=1+3=4.

Аналогично находим графы:

,

 

Поскольку i=8=n(G), работа алгоритма заканчивается.

 

Таким образом, искомое минимальное остовное дерево графа G − граф G8, длина которого равна 22.


Дата добавления: 2015-10-13; просмотров: 121 | Нарушение авторских прав


Читайте в этой же книге: Способы представления графов в памяти | Матрица смежности | Списки смежности | Просмотр графа | Обход (поиск) в ширину | Задача нахождения кратчайшего пути. Алгоритм Дейкстры | Программа поиска минимального пути в графе между заданными вершинами |
<== предыдущая страница | следующая страница ==>
Топологическая сортировка| Программа поиска всевозможных путей в графе

mybiblioteka.su - 2015-2024 год. (0.005 сек.)