Algoritmo do peso das arestas: Conceito e resolução de problemas
Explicação
Dado um grafo podemos associar a cada aresta um número, que é denominado o peso da aresta. O grafo juntamente com esta informação chama-se grafo ponderado ou pesado.
Num grafo completo de n vértices (com n≥3), o número de circuitos hamiltonianos pesados diferentes é dado por
2(n−1)!=(n−1)×(n−2)×(n−3)×...×4×3
Nota: Mais precisamente, a fórmula acima dá o número de circuitos hamiltonianos pesados diferentes quando se contam todos os circuitos-espelho com um único circuito. Um circuito-espelho é um circuito em que as letras se leem de trás para a frente (e, por isso, estes circuitos existem em qualquer grafo não orientado).
Problemas clássicos em teoria de grafos
Os grafos hamiltonianos são aplicados frequentemente em problemas como o seguinte.
Exemplo
Atenta no problema do caixeiro-viajante:
"Um caixeiro-viajante pretende visitar n cidades iniciando e terminando a sua viagem na mesma cidade. Supõe que a ordem das visitas às cidades não é importante e que qualquer uma das cidades tem ligação com as restantes. Como pode fazer este percurso na menor distância possível?"
Considera n=4 e que o caixeiro-viajante vive em A, sendo os pesos das arestas a distância entre as cidades em km.
Existem seis circuitos hamiltonianos possíveis:
Circuito | Circuito-espelho correspondente |
ABCDA=12+9+1+3=25ABDCA=12+4+1+7=24ACBDA=7+9+4+3=23 | ADCBA=3+1+9+12=25ACDBA=7+1+4+12=24ADBCA=3+4+9+7=23 |
Este grafo hamiltoniano tem 3 circuitos pesados diferentes (6 circuitos :2=3). Nota que há dois circuitos com menor peso, ACBDA e o seu circuito-espelho ADBCA, concluindo-se que o caixeiro pode fazer a sua viagem com a distância mínima de 23 km.
Algoritmos de minimização
Para que não fosse necessário considerar todos os circuitos possíveis (o que seria um processo moroso para n muito grande), criaram-se algoritmos de minimização.
Repara que os algoritmos aqui descritos permitem-te obter apenas circuitos hamiltonianos de peso reduzido, sem a garantia de que serão a solução ótima (a de menor peso) para o problema.
Algoritmo da cidade mais próxima
Neste algoritmo, escolhe-se a aresta mais leve consoante a cidade em que se está.
Procedimento
1.
| Escolhe a cidade de partida; |
2. | Escolhe a aresta de menor peso possível que te permite visitar a cidade seguinte; |
3. | Repete o passo 2 até teres visitado todas as cidades, voltando à cidade inicial e certificando-te que não houve nenhuma repetição. |
Exemplo
Iniciando o percurso em A, a aresta de menor peso que permite visitar outra cidade é AD. Da mesma forma, escolhe-se a aresta DC e, de seguida, para que se visite uma nova cidade, escolhe-se a aresta CB. Por fim, apenas falta concluir o circuito, sendo utilizada a aresta BA. Assim, o circuito formado é ADCBA, cujo peso é 25.
Algoritmo do peso das arestas
Neste algoritmo, constrói-se o circuito ordenando primeiro as arestas de forma crescente do seu peso e só depois escolhendo as cidades a visitar.
Procedimento
1. | Ordena as arestas pelos seus pesos; |
2. | Escolhe as arestas de menor peso que verifiquem as condições: a) um vértice nunca aparece três vezes; b) não se fecha o circuito com vértices por visitar; c) todos os vértices são visitados apenas uma vez. |
3. | Ordena a solução conforme o vértice de partida escolhido. |
Exemplo
Aplicando o algoritmo ao exemplo anterior, começamos por ordenar as arestas por ordem crescente de peso:
CD:1AD:3DB:4AC:7CB:9AB:12
Para o passo 2, escolhemos as arestas AD, DB, BC e CA.
O circuito obtido pelo algoritmo é então ADBCA, cujo peso é 23.
Nota: neste caso, o algoritmo do peso das arestas escolheu a solução ótima para o problema, No entanto, é importante realçar que, em geral, o algoritmo resulta em circuitos de peso reduzido e não necessariamente ótimos.