Árvore de extensão

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

Três exemplos em um grafo de grade quadrada 8x8

Uma árvore de extensão, árvore geradora 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, árvore geradora 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 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 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 árvore de extensão 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 árvore de extensão (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 árvore de extensão.

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)