Найти минимальное связующее дерево в объекте-биографе
[Tree, pred] = minspantree(BGObj)
[Tree, pred] = minspantree(BGObj, R)
[Tree, pred] = minspantree(..., 'Method', MethodValue, ...)
[Tree, pred] = minspantree(..., 'Weights', WeightsValue, ...)
BGObj | Объект-биограф, созданный biograph (конструктор объекта). |
R | Скаляр между 1 и числом узлов. |
Совет
Вводные сведения о функциях теории графов см. в разделе Функции теории графов.
[ находит ациклическое подмножество рёбер, которое соединяет все узлы в неориентированном графе, представленном матрицей близости N-на-N, извлеченной из объекта-биографа, Tree, pred] = minspantree(BGObj)BGObjи для которых общий вес минимизирован. Все веса рёбер являются ненулевыми элементами в нижнем треугольнике разреженной матрицы N-by-N. Продукция Tree - покрывающее дерево, представленное разреженной матрицей. Продукция pred - вектор, содержащий предшествующие узлы минимального покрывающего дерева (MST), корневой узел которого обозначен 0. Корневой узел по умолчанию является первым узлом в самом большом подключенном компоненте. Для этого вычисления требуется дополнительный вызов graphconncomp функция.
Примечание
Функция игнорирует направление ребер в объекте Biograph.
[ задает корень минимального связующего дерева для узла Tree, pred] = minspantree(BGObj, R)R.
[ требования Tree, pred] = minspantree(..., 'PropertyName', PropertyValue, ...)minspantree с необязательными свойствами, использующими пары имя/значение свойства. Можно указать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и не чувствителен к регистру. Эти пары имя/значение свойства следующие:
[ позволяет указать алгоритм, используемый для поиска минимального покрывающего дерева (MST). Возможны следующие варианты:Tree, pred] = minspantree(..., 'Method', MethodValue, ...)
'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] = minspantree(..., 'Weights', WeightsValue, ...)WeightsValue - вектор столбца, имеющий одну запись для каждого ненулевого значения (ребра) в разреженной матрице N-by-N. Порядок пользовательских весов в векторе должен соответствовать порядку ненулевых значений в разреженной матрице N-на-N, когда она проходит по столбцам. По умолчанию minspantree получает информацию о весе из ненулевых записей в разреженной матрице N-by-N.
[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).
allshortestpaths | biograph | conncomp | graphminspantree | isdag | isomorphism | isspantree | maxflow | shortestpath | topoorder | traverse