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

Conteúdo apagado Conteúdo adicionado
YurikBot (discussão | contribs)
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 [[algoritmo de Kruskal]]. Todos são [[algoritmo guloso|algoritmos gulosos]] que rodam em tempo polinomial, então o problema de encontrar tais árvores é de complexidade [[p (complexidade)|P]].
 
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'').