minspantree

Árvore geradora mínima de um grafo com pesos.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

T = minspantree(G)

Descrição

Uma árvore geradora conecta todos os nós com o menor número de arestas, e a mínima faz isso com a menor soma de pesos possível. É a maneira mais barata de interligar um conjunto de locais. Para um grafo desconexo o resultado é uma floresta com uma árvore por componente.

Quando várias árvores empatam, qualquer uma delas pode ser devolvida.

Argumentos de entrada

G

Um graph não direcionado. Os pesos das arestas, se existirem, são minimizados; caso contrário todas as arestas pesam igual.

Argumentos de saída

T

Um grafo com os nós de G e um subconjunto de suas arestas: numnodes(G) - c arestas para c componentes conexos, sem ciclos.

Exemplo

A rede mais barata

G = graph([1 1 2 2 3 4], [2 3 3 4 4 5], [2 1 3 5 1 4]);
T = minspantree(G);
disp(T.Edges)
sum(T.Edges.Weight)

    EndNodes    Weight
    ________    ______

     1    2       2   
     1    3       1   
     3    4       1   
     4    5       4   
ans = 8

Veja também

graph shortestpath conncomp maxflow