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

Aplicações[editar | editar código-fonte]

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. [1]

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[editar | editar código-fonte]