Árvore de extensão

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Exemplo de uma árvore de dispersão (composta pelas arestas azuis)

Uma árvore de extensão ou árvore de dispersão (em inglês: spanning tree) é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices.

Uma árvore de extensão mínima ou árvore de extensão de custo mínimo (em inglês: minimum spanning tree) é o subconjunto de arestas de menor peso total em um grafo valorado que forma uma árvore contendo todos os nós.

Uma árvore de extensão/dispersão apresenta as seguintes propriedades:

  • Define um subconjunto de arestas que mantém o grafo conectado em um único componente;
  • Em um grafo não-valorado qualquer árvore de dispersão é mínima;
  • Podem ser calculadas em tempo polinomial;

Os algoritmos usuais para a determinação de árvores de extensão/dispersão são o algoritmo de Prim (1957) e o algoritmo de Kruskal (1956).

Referências[editar | editar código-fonte]