minspantree

Минимальное покрывающее дерево графа

Описание

пример

T = minspantree(G) возвращает минимальное дерево охвата, T, для графика G.

пример

T = minspantree(G,Name,Value) дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение". Например, minspantree(G,'Method','sparse') алгоритм Краскэла использования для вычисления минимального дерева охвата.

пример

[T,pred] = minspantree(___) также возвращает вектор из узлов-предшественников, pred, использование любого из входных параметров в предыдущих синтаксисах.

Примеры

свернуть все

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

s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = graph(s,t,weights);
p = plot(G,'EdgeLabel',G.Edges.Weight);

Вычислите и постройте минимальное дерево охвата графика сверху графика. T содержит те же узлы как G, но подмножество ребер.

[T,pred] = minspantree(G);
highlight(p,T)

Создайте и постройте график, который имеет несколько компонентов.

s = {'a' 'a' 'a' 'b' 'b' 'c' 'e' 'e' 'f' 'f' 'f' 'f' 'g' 'g'};
t = {'b' 'c' 'd' 'c' 'd' 'd' 'f' 'g' 'g' 'h' 'i' 'j' 'i' 'j'};
G = graph(s,t);
p = plot(G,'Layout','layered');

Найдите минимальный лес охвата для графика, запускающегося в узле i. Подсветите получившийся лес в графике. Имена узла графика перенесены в минимальный древовидный граф охвата.

[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i'));
highlight(p,T)

Используйте вектор из узлов-предшественников, pred, создать направленную версию минимального леса охвата. Все ребра в этом дереве направлены далеко от корневых узлов в каждом компоненте (узлы i и a).

rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name);
plot(rootedTree)

Входные параметры

свернуть все

Введите график в виде graph объект. Используйте graph создать объект неориентированного графа.

Пример: G = graph(1,2)

Аргументы в виде пар имя-значение

Задайте дополнительные разделенные запятой пары Name,Value аргументы. Name имя аргумента и Value соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: [T,pred] = minspantree(G,'Method','sparse')

Минимальный алгоритм связующего дерева в виде разделенной запятой пары, состоящей из 'Method' и одна из опций в таблице.

ОпцияОписание
'dense' (значение по умолчанию)Алгоритм Прима. Этот алгоритм запускается в корневом узле и добавляет ребра в дерево при пересечении графика.
'sparse'Алгоритм Краскэла. Эти виды алгоритма все ребра в развес, и затем добавляют их в дерево, если они не создают цикл.

Корневой узел в виде разделенной запятой пары, состоящей из 'Root' и индекс узла или имя узла. Корневым узлом по умолчанию является 1.

  • Если 'Method' 'dense' (значение по умолчанию), затем корневой узел является стартовым узлом.

  • Если 'Method' issparse , затем корневой узел используется только, чтобы вычислить pred, вектор из узлов-предшественников.

Можно задать корневой узел в любом из этих форматов:

ЗначениеПример
Скалярный индекс узла1
Имя узла вектора символов'A'
Имя узла строкового скаляра"A"

Тип минимального дерева охвата в виде разделенной запятой пары, состоящей из 'Type' и одна из опций в таблице.

ОпцияОписание
'tree'

Только одно дерево возвращено. Дерево содержит корневой узел.

'forest'

Лес минимальных деревьев охвата возвращен. Другими словами, задайте 'forest' вычислить минимальное дерево охвата всех связанных компонентов в графике.

Выходные аргументы

свернуть все

Минимальное дерево охвата, возвращенное как graph объект.

Узлы-предшественники, возвращенные как вектор из индексов узла. pred(I) индекс узла предшественника узла I. Условно, pred(rootNode) = 0. Если Type 'tree', затем pred(I) = NaN для всех узлов I это не находится в том же компоненте как корневой узел.

pred задает направленную версию минимального дерева охвата, со всеми ребрами, направленными далеко от корневого узла.

Больше о

свернуть все

Минимальное дерево охвата

Для связных графов дерево охвата является подграфом, который соединяет каждый узел в графике, но не содержит циклов. Может быть много деревьев охвата для любого данного графика. Путем присвоения веса каждому ребру различным деревьям охвата присваивают номер для общей массы их ребер. Минимальное дерево охвата является затем деревом охвата, ребра которого имеют наименьшее количество общей массы.

Для графиков с равным весом ребра все деревья охвата являются минимальными деревьями охвата, начиная с пересечения n узлы требуют n-1 края.

Смотрите также

| |

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