Árvore de extensão

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.

Exemplo de uma árvore de dispersão (composta pelas arestas azuis)

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).

Aplicações

Vários algoritmos de busca de caminho, incluindo o algoritmo de Dijkstra e o algoritmo A*, desenvolvem internamente uma spanning tree como uma etapa intermediária para resolver o problema.

Para minimizar o custo de redes de energia, conexões cabeadas, tubulação, reconhecimento automático de fala, etc., as pessoas geralmente usam algoritmos que gradualmente constroem uma spanning tree (ou muitas dessas árvores) como passo intermediário no processo de encontrar a árvore de extensão mínima.

A Internet e muitas outras redes de telecomunicações possuem links de transmissão que conectam nós em uma topologia de malha (mesh) que inclui alguns loops. Para evitar loops de ponte e de roteamento, muitos protocolos de roteamento projetados para essas redes -- incluindo o protocolo Spanning Tree, Open Shortest Path First, protocolo de roteamento de estado de link, roteamento com base em árvore aumentada, etc. -- exigem um roteador para lembrar a spanning tree.

Referências

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