graphminspantree

Найти минимальное связующее дерево в графике

Синтаксис

[Tree, pred] = graphminspantree(G) [Tree, pred] = graphminspantree(G, R) [Tree, pred] = graphminspantree(..., 'Method', MethodValue, ...) [Tree, pred] = graphminspantree(..., 'Weights', WeightsValue, ...)

Аргументы

`G`	N-на-N разреженная матрица, представляющая неориентированный граф. Ненулевые записи в матрице `G` представляют веса кромок.
`R`	Скаляр между 1 и числом узлов.

Описание

Совет

Вводные сведения о функциях теории графов см. в разделе Функции теории графов.

[Tree, pred] = graphminspantree(G) находит ациклическое подмножество рёбер, которое соединяет все узлы в неориентированном графе G и для которых общий вес минимизирован. Все веса рёбер являются ненулевыми элементами в нижнем треугольнике разреженной матрицы N-by-N G. Продукция Tree - покрывающее дерево, представленное разреженной матрицей. Продукция pred - вектор, содержащий предшествующие узлы минимального покрывающего дерева (MST), корневой узел которого обозначен 0. Корневой узел по умолчанию является первым узлом в самом большом подключенном компоненте. Для этого вычисления требуется дополнительный вызов graphconncomp функция.

[Tree, pred] = graphminspantree(G, R) задает корень минимального связующего дерева для узла R.

[Tree, pred] = graphminspantree(..., 'PropertyName', PropertyValue, ...) требования graphminspantree с необязательными свойствами, использующими пары имя/значение свойства. Можно указать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и не чувствителен к регистру. Эти пары имя/значение свойства следующие:

[Tree, pred] = graphminspantree(..., 'Method', MethodValue, ...) позволяет указать алгоритм, используемый для поиска минимального покрывающего дерева (MST). Возможны следующие варианты:

'Kruskal' - Выращивает минимальное покрывающее дерево (MST) по одному краю за раз, находя край, который соединяет два дерева в растущем лесу растущих MST. Сложность времени O(E+X*log(N)), где X - количество краев не длиннее самого длинного края в MST, и N и E - количество узлов и рёбер соответственно.
'Prim' - Алгоритм по умолчанию. Выращивает минимальное связующее дерево (MST) по одному краю за раз, добавляя минимальное ребро, которое соединяет узел в растущем MST с любым другим узлом. Сложность времени O(E*log(N)), где N и E - количество узлов и рёбер соответственно.

Примечание

Когда граф не связан, алгоритм Прима возвращает только дерево, которое содержит R, в то время как алгоритм Крускала возвращает MST для каждого компонента.

[Tree, pred] = graphminspantree(..., 'Weights', WeightsValue, ...) позволяет задать пользовательские веса для ребер. WeightsValue является вектором-столбцом, имеющим одну запись для каждого ненулевого значения (ребра) в матрице G. Порядок пользовательских весов в векторе должен соответствовать порядку ненулевых значений в матрице G при пересечении по столбцам. По умолчанию graphminspantree получает информацию о весе из ненулевых записей в матрице G.

Примеры

Создайте и просмотрите неориентированный график с 6 узлами и 11 ребрами.

W = [.41 .29 .51 .32 .50 .45 .38 .32 .36 .29 .21];
DG = sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],W);

UG = tril(DG + DG')
UG =

   (2,1)       0.4100
   (4,1)       0.4500
   (6,1)       0.2900
   (3,2)       0.5100
   (5,2)       0.3200
   (6,2)       0.2900
   (4,3)       0.5000
   (5,3)       0.3200
   (5,4)       0.3600
   (6,4)       0.3800
   (6,5)       0.2100

view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

Найдите и просмотрите минимальное покрывающее дерево неориентированного графика.

 [ST,pred] = graphminspantree(UG)

ST =

   (6,1)       0.2900
   (6,2)       0.2900
   (5,3)       0.3200
   (5,4)       0.3600
   (6,5)       0.2100


pred =

     0     6     5     5     6     1

view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'))

Ссылки

[1] Крускал, Дж. Б. (1956). В самом коротком вложенном дереве графика и проблемы с коммивояжером. Труды Американского математического общества 7, 48-50.

[2] Прим, Р. (1957). Сети кратчайшего соединения и некоторые обобщения. Bell System Technical Journal 36, 1389-1401.

[3] Сиек, Дж. Г. Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

Представлен в R2006b

Документация