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

Conteúdo apagado Conteúdo adicionado
Linha 1:
{{fusão|Árvore de cobertura mínima}}
[[Image:Minimum spanning tree.svg|thumb|300px|right|A árvore de extensão mínima de um grafo plano. Cada aresta é identificada como seu peso, o qual é aproximadamente igual ao seu comprimento.]]
Dado um [[grafo unidirecional]] [[grafo conectado|conectado]], [[árvore de extensão (matemática)|árvore de extensão]] deste grafo é um [[subgrafo]] o qual é uma [[grafoárvore de(teoria árvoredos grafos|árvore]] que conecta todos os vértices. Um único grafo pode ter diferentes árvore de extensão. Nos podemos assinalar um ''peso'' a cada aresta, que é um número que representa quão desfavorável ela é, e atribuir um peso a árvore de extensão calculado pela soma dos pesos das arestas que a compõem. Uma '''árvore de extensão mínima''' ou '''árvore de extensão de peso mínimo''' é então uma árvore de extensão com peso menor ou igual a cada uma das outras árvores de extensão. Generalizando mais, qualquer grafo não direcional tem uma '''floresta de árvores mínimas'''. Em um grafo não ponderado (sem peso nas arestas), qualquer árvore de extensão é mínima.
 
== Algoritmos ==