Árvore de extensão
De Wikipedia, a enciclopédia encyclopedia
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).