minspantree (biograph)

Найдите минимальное дерево охвата в биообъекте диаграмм

Синтаксис

[Tree, pred] = minspantree(BGObj)
[Tree, pred] = minspantree(BGObj, R)
[Tree, pred] = minspantree(..., 'Method', MethodValue, ...)
[Tree, pred] = minspantree(..., 'Weights', WeightsValue, ...)

Аргументы

BGObj Биообъект диаграмм, созданный biograph Конструктор Object.
RСкаляр между 1 и количество узлов.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[Tree, pred] = minspantree(BGObj) находит нециклическое подмножество ребер, которое соединяет все узлы в неориентированном графе, представленном N на n матрицей смежности, извлеченной из биообъекта диаграмм, BGObj, и для которого минимизирована общая масса. Веса ребер являются всеми ненулевыми записями в более низком треугольнике N на n разреженной матрицы. Выведите Tree дерево охвата, представленное разреженной матрицей. Выведите pred вектор, содержащий узлы-предшественников минимального дерева охвата (MST), с корневым узлом, обозначенным 0. Значения по умолчанию корневого узла к первому узлу в самом большом связанном компоненте. Этот расчет требует дополнительного вызова graphconncomp функция.

Примечание

Функция игнорирует направление ребер в Биообъекте диаграмм.

[Tree, pred] = minspantree(BGObj, R) устанавливает корень минимального дерева охвата к узлу R.

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

[Tree, pred] = minspantree(..., 'Method', MethodValue, ...) позволяет вам указать, что алгоритм раньше находил минимальное дерево охвата (MST). Выбор:

  • 'Kruskal' — Выращивает минимальное дерево охвата (MST) одно ребро за один раз путем нахождения ребра, которое соединяет два дерева в распространяющемся лесу роста MSTs. Временной сложностью является 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] Kruskal, J.B. (1956). На самом коротком поддереве охвата графика и проблемы коммивояжера. Продолжения американского математического общества 7, 48-50.

[2] Чопорный, R. (1957). Самые короткие сети связи и некоторые обобщения. Система Bell технический журнал 36, 1389-1401.

[3] Siek, Дж.Г. Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Представленный в R2006b
Для просмотра документации необходимо авторизоваться на сайте