3.3.3. Минимальные остовные деревья нагруженных графов

Пусть теперь каждому ребру x Î X связного графа G=(V,X) c непустым множеством ребер Х поставлена в соответствие величина l(x) – длина ребра х, т.е. граф G является нагруженным.

Определение. Остовное дерево связного нагруженного граф G с минимальной суммой длин содержащихся в нем ребер будем называть минимальным остовным деревом (МОД) графа G.

Алгоритм выделения МОД нагруженного связного графа G:

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

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

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

Пример 89.

Определить МОД нагруженного графа G, изображенного на рисунке 41, используя алгоритм.

Решение.

На рисунке 42 приведена последовательность графов Gi, i=2,3,4,5, получаемых в результате выполнения алгоритма. При этом в силу того, что n(G)=5, G5 - МОД графа G. Причем, МОД(G) = 7.

Замечание. Возможно выделить в графе несколько остовных деревьев, каждое из которых будет являться минимальным, при этом величина МОД для всех этих деревьев будет равной.

Замечание. Для выделения МОД нагруженного псевдографа G следует предварительно удалить из G петли, из кратных ребер оставить лишь ребра минимальной длины.