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\geq 3$ ), o número de circuitos hamiltonianos pesados diferentes é dado por

$\dfrac{(n-1)!}{2}=(n-1)\times(n-2)\times(n-3)\times...\times4\times3$

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$ .

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Algoritmo do peso das arestas: Conceito e resolução de problemas

Existem seis circuitos hamiltonianos possíveis:

Circuito	Circuito-espelho correspondente
$\begin{aligned}& \text{ABCDA}=12+9+1+3=25 \\ \\ & \text{ABDCA}=12+4+1+7=24 \\ \\ & \text{ACBDA}=7+9+4+3=23\end{aligned}$	$\begin{aligned}& \text{ADCBA}=3+1+9+12=25\\ \\ & \text{ACDBA}=7+1+4+12=24 \\ \\ & \text{ADBCA}=3+4+9+7=23\end{aligned}$

Este grafo hamiltoniano tem $3$ circuitos pesados diferentes ( $6$ circuitos $:2=3$ ). Nota que há dois circuitos com menor peso, $\text{ACBDA}$  e o seu circuito-espelho $\text{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 $\text{A}$ , a aresta de menor peso que permite visitar outra cidade é $\text{AD}$ . Da mesma forma, escolhe-se a aresta $\text{DC}$ e, de seguida, para que se visite uma nova cidade, escolhe-se a aresta $\text{CB}$ . Por fim, apenas falta concluir o circuito, sendo utilizada a aresta $\text{BA}$ . Assim, o circuito formado é $\text{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:

$\begin{aligned}& \text{CD}: 1 \\& \text{AD}: 3 \\& \text{DB}: 4 \\& \text{AC}: 7 \\& \text{CB}: 9 \\& \text{AB}: 12 \end{aligned}$

Para o passo 2, escolhemos as arestas $\text{AD,\ DB,\ BC}$ e $\text{CA}$ .

O circuito obtido pelo algoritmo é então $\text{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.