Árvore de extensão: diferenças entre revisões

 

Uma spanning tree:

 

- Define o subconjunto mais barato de arestas que mantém o grafo conectado em um único componente;

- Em um grafo não-valorado qualquer spanning tree é mínimo;

- Podem ser calculadas em tempo polinomial;

- Algoritmos usuais: Prim(1957) e Kruskal(1956).