𝖂𝖎ƙ𝖎𝖊

Á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 Predefinição:Língua com nome) é 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 Predefinição:Língua com nome) é 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. [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

  1. R. L. Graham and Pavol Hell. "On the History of the Minimum Spanning Tree Problem". 1985.

talvez você goste