Árvore de extensão mínima: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: sv:Minimalt uppspännande träd |
|||
Linha 1:
[[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 de árvore|á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 ==
O primeiro algoritmo a encontra uma arvore de extensão minima foi desenvolvido pelo cientista Checo [[Otakar Borůvka]] em [[1926]] (veja [[algoritmo de Boruvka]]). Seu propósito era fornecer uma cobertura elétrica eficiente da [[Bohemia]]. Existem hoje dois algoritmos comumente usados, [[algoritmo de Prim]] e
O mais rápido algoritmo de árvore mínima de extensão foi desenvolvido por [[Bernard Chazelle]], e foi baseado no algoritmo de Borůvka's. Ele roda em um tempo de ''[[notação O |O]]''(''m'' α(''m'',''n'')), onde ''m'' é o número de arestas, ''n'' refere-se ao numero de vértices e α é a clássica função inversa da [[função de Ackermann]]. A função α cresce de forma extremamente lenta, então para todos os propósitos práticos ele pode ser considerado uma constante não maior que quatro; portanto o algoritmo de Chazelle chega muito perto de um tempo ''O''(''m'').
|