Árvore de extensão: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
← nova página: spanning tree é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices. minimum spanning tree: é o subconjunto de arestas de menor ... |
|||
Linha 2:
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 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).
| |||