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

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

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.

Пример.

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

Обозначим ребро, соединяющее вершины v_i и v_j через x_ij.

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

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

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

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

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

,

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

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

Дата добавления: 2015-10-13