3.3.3. Минимальные остовные деревья нагруженных графов
Пусть теперь каждому ребру x Î X связного графа G=(V,X) c непустым множеством ребер Х поставлена в соответствие величина l(x) – длина ребра х, т.е. граф G является нагруженным.
Приведем алгоритм, позволяющий найти остовное дерево графа G с минимальной суммой длин содержащихся в нем ребер (по сравнению со всеми другими остовными деревьями графа 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 петли, из кратных ребер оставить лишь ребра минимальной длины.