Problemas de Árvore Mínima e o Algoritmo de Kruskal

Prévia do material em texto

Problemas de árvore mínima 
 
Problemas de árvore mínima consistem em situações onde o objetivo é 
interligar todos os nós de um grafo com o menor custo possível. 
Problemas assim aparecem com muita frequência em diversas situações: 
 
 Interligar computadores de uma rede com o menor gasto referente ao 
cabeamento. 
 
 Conectar caixas eletrônicos de um determinado banco. 
 
 Instalar um sistema de segurança nas residências de um condomínio. 
 
 Interligar máquinas, equipamentos e computadores de uma empresa. 
 
O algoritmo mais utilizado para que se possa obter a solução de um 
problema de árvore mínima é o algoritmo de Kruskal. O algoritmo consiste em 
ligar todos os nós de um grafo onde a soma dos custos referentes às conexões 
entre dois nós é o menor possível. 
O princípio básico do algoritmo de Kruskal consiste em, a partir de um 
grafo com pesos, isto é, com custos associados a cada arco, a cada iteração 
marcar o arco de menor custo. Caso haja formação de ciclo, eliminar os 
respectivos arcos. Em seguida, repetir esse processo até que todos os arcos 
estejam marcados ou eliminados. 
Para ilustrar melhor, vamos considerar o seguinte problema: Uma 
companhia de TV a Cabo está instalando decodificadores nas residências de um 
condomínio. A figura a baixo ilustra as localizações de cada decodificador e os 
respectivos custos, em reais. Determine como o técnico da empresa deve 
proceder para que todas as residências fiquem interligadas e o custo total de 
instalação seja o menor possível. 
 
 
 
 
O primeiro passo é determinar qual é a conexão de menor custo. 
Observando a figura, vemos que o arco C-E tem um custo igual a 4. 
Marcamos esse arco. 
 
 
 
O próximo passo é determinar o próximo arco de menor custo. Observe 
que os arcos A-B e E-F têm um custo igual a 5. Nesse caso escolheremos ao 
acaso o arco A-B. 
 
 
 
O próximo arco a ser escolhido é o arco E-F. 
 
 
 
Como não podemos fechar um ciclo, devemos eliminar o arco C-F. 
 
 
 
O próximo arco a ser escolhido é B-D ou D-E, ambos com custo igual a 
6. Escolheremos, ao acaso, o arco B-D. 
 
 
 
O próximo passo é escolher agora o arco D-E, também de custo igual a 
6. 
 
 
 
Note que agora precisaremos eliminar alguns arcos. Primeiramente 
iremos eliminar o arco B-E. 
 
 
 
Como ainda temos a possibilidade de fechar um ciclo, iremos eliminar o 
arco A-E. 
 
 
 
Devemos fazer o mesmo para o arco A-C, pois também forma um ciclo. 
 
 
 
Dentre os arcos restantes, o de menor custo é o D-G. Marcamos então 
esse arco. 
 
 
 
Agora, para não formar ciclo, devemos eliminar o arco E-G. 
 
 
 
Faremos o mesmo com o arco F-G. 
 
 
 
Como todos os arcos foram marcados ou eliminados, obtivemos a 
solução ótima do problema de árvore mínima. 
 
 
 
Os nós a serem interligados são A-B, B-D, C-E, D-E, D-G e E-F, com um 
custo mínimo de 5+6+4+6+7+5 que totaliza R$ 33,00 referentes à instalação 
dos decodificadores.