Минимальное покрывающее дерево графика
T = minspantree(G)T, для графика G.
T = minspantree(G,Name,Value)minspantree(G,'Method','sparse') использует алгоритм Крускала для вычисления минимального покрывающего дерева.
Создайте и постройте график куба с взвешенными ребрами.
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)
