Árvore de extensão

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

• Eppstein, David (1999). "Spanning trees and spanners". Handbook of Computational Geometry: 425–461, Elsevier. 
• Garey, Michael R.; Johnson, David S.. Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: W.H. Freeman, 1979. ISBN 0-7167-1045-5 A2.1: ND2, pg.206.
• Wu, Bang Ye; Chao, Kun-Mao. Spanning Trees and Optimization Problems. [S.l.]: CRC Press, 2004. ISBN 1584884363