Нахождение минимального покрывающего дерева в объекте биографика
[
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 на N. Выходные Tree
является покрывающим деревом, представленным разреженной матрицей. Выходные pred
- вектор, содержащий предшествующие узлы минимального покрывающего дерева (MST) с корневым узлом, обозначенным 0
. Корневой узел по умолчанию является первым узлом в самом большом связном компоненте. Для этот расчет требуется дополнительный вызов graphconncomp
функция.
Примечание
Функция игнорирует направление ребер в объекте Биографик.
[
устанавливает корень минимального покрывающего дерева в узел 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 на N. Порядок пользовательских весов в векторе должен совпадать с порядком ненулевых значений в разреженной матрице N на N, когда она пройдена по столбцу. По умолчанию minspantree
получает информацию о весе из ненулевых значений в разреженной матрице N на N.
[1] Крускаль, Дж. Б. (1956). На самом коротком покрывающем поддереве графика и задачи коммивояжера. Труды Американского математического общества 7, 48-50.
[2] Прим, Р. (1957). Кратчайшие сети соединений и некоторые обобщения. Bell System Technical Journal 36, 1389-1401.
[3] Siek, J.G. Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).
allshortestpaths
| biograph
| conncomp
| graphminspantree
| isdag
| isomorphism
| isspantree
| maxflow
| shortestpath
| topoorder
| traverse