Árvore de cobertura mínima
Uma série de problemas da teoria dos gráficos são chamados de árvore de amplitude mínima. Na teoria dos gráficos, uma árvore é uma forma de conectar todos os vértices juntos, de modo que haja exatamente um caminho de qualquer vértice, para qualquer outro vértice da árvore. Se o gráfico representa um número de cidades conectadas por estradas, pode-se selecionar um número de estradas, de modo que cada cidade possa ser alcançada de todas as outras, mas que não haja mais que uma maneira de viajar de uma cidade para outra.
Um gráfico pode ter mais de uma árvore, assim como pode haver mais de uma maneira de selecionar as estradas entre as cidades.
Na maioria das vezes, os gráficos são ponderados; cada conexão entre duas cidades tem um peso: pode custar algo para viajar em uma determinada estrada, ou uma conexão pode ser mais longa que a outra, o que significa que leva mais tempo para viajar nessa conexão. Na linguagem da teoria dos gráficos, as conexões são chamadas de bordas.
Uma árvore com o espaçamento mínimo é uma árvore. É diferente das outras árvores, pois minimiza o total dos pesos presos às bordas. Dependendo do aspecto do gráfico, pode haver mais de uma árvore de envergadura mínima. Em um gráfico onde todas as bordas têm o mesmo peso, cada árvore é uma árvore com o mínimo de largura. Se todas as bordas tiverem pesos diferentes (isto é: não há duas bordas com o mesmo peso), há exatamente uma árvore de ventania mínima.
A árvore mínima de um gráfico planar. Cada borda é rotulada com seu peso, que aqui é aproximadamente proporcional ao seu comprimento.
Encontrar o espaçamento mínimo da árvore
Uma primeira tentativa
Pode ser muito simples fazer um algoritmo que irá descobrir uma árvore de espaçamento mínimo:
função MST(G,W) : T = { } enquanto que T não forma uma árvore de envergadura: encontrar a borda mínima ponderada em E que é segura para T T = T união {(u,v) } retorno TNeste caso, "seguro" significa que a inclusão da borda não forma um ciclo no gráfico. Um ciclo significa começar em um vértice, viajar para vários outros vértices e terminar no ponto de partida novamente sem usar a mesma borda duas vezes.
História
O cientista tcheco Otakar Borůvka desenvolveu o primeiro algoritmo conhecido para encontrar uma árvore de espaçamento mínimo, em 1926. Ele queria resolver o problema de encontrar uma cobertura eficiente da Moravia com eletricidade. Hoje, este algoritmo é conhecido como o algoritmo do Borůvka. Dois outros algoritmos são comumente usados hoje em dia. Um deles foi desenvolvido por Vojtěch Jarník em 1930, e colocado em prática por Robert Clay Prim em 1957. Edsger Wybe Dijkstra redescobriu-o em 1959, e chamou-o de algoritmo do Prim. O outro algoritmo é chamado de algoritmo de Kruskal, e foi puxado por Joseph Kruskal em 1956. Todos os três algoritmos são gananciosos, e funcionam em tempo polinomial.
O algoritmo de árvore de cobertura mínima mais rápido até o momento foi desenvolvido por Bernard Chazelle. O algoritmo é baseado na pilha macia, uma fila de prioridade aproximada. Seu tempo de execução é O(m α(m,n)), onde m é o número de bordas, n é o número de vértices e α é o clássico inverso funcional da função Ackermann. A função α cresce extremamente lentamente, de modo que para todos os fins práticos ela pode ser considerada uma constante não superior a 4; assim, o algoritmo de Chazelle leva um tempo muito próximo do linear.
Qual é o algoritmo mais rápido possível para este problema? Essa é uma das perguntas mais antigas em aberto na ciência da computação. Existe claramente um limite inferior linear, uma vez que devemos ao menos examinar todos os pesos. Se os pesos de borda são inteiros com um comprimento de bit delimitado, então os algoritmos determinísticos são conhecidos com tempo de execução linear. Para pesos gerais, existem algoritmos randomizados cujo tempo de execução esperado é linear.
O problema também pode ser abordado de forma distribuída. Se cada nó for considerado um computador e nenhum nó souber de nada, exceto de seus próprios links conectados, ainda será possível calcular a árvore de abrangência mínima distribuída.
Perguntas e Respostas
P: O que é uma árvore de extensão mínima na teoria dos gráficos?
R: Uma árvore de extensão mínima é uma árvore que minimiza os pesos totais associados às bordas na teoria dos grafos.
P: O que é uma árvore na teoria dos grafos?
R: Uma árvore é uma forma de conectar todos os vértices na teoria dos gráficos, de modo que haja apenas um caminho de qualquer vértice para qualquer outro vértice da árvore.
P: Qual é o objetivo de selecionar estradas em um cenário de teoria dos grafos que representa cidades?
R: O objetivo da seleção de estradas em um cenário de teoria dos grafos que representa cidades é permitir que cada cidade seja alcançada a partir de todas as outras, mas sem mais de um caminho possível para viajar de uma cidade para outra.
P: Um gráfico pode ter mais de uma árvore de abrangência?
R: Sim, um gráfico pode ter mais de uma árvore de abrangência.
P: Qual é a diferença entre uma árvore de extensão mínima e outras árvores na teoria dos grafos?
R: Uma árvore de extensão mínima minimiza os pesos totais associados às bordas, enquanto outras árvores não têm esse recurso.
P: O que são bordas na teoria dos gráficos?
R: As bordas são as conexões entre dois vértices na teoria dos gráficos.
P: Pode haver mais de uma árvore de extensão mínima em um gráfico com bordas de pesos diferentes?
R: Sim, dependendo da aparência do gráfico, pode haver mais de uma árvore de extensão mínima.
