Matemtica Aplicada s Cincias

Sociais Texto de Apoio

Assunto: Grafos de Hamilton

1. Chama-se Caminho Hamiltoniano a um caminho que percorre todos os vrtices de um

grafo no repetindo nenhum deles.

2. Chama-se Circuito Hamiltoniano a um caminho hamiltoniano que comea e acaba no

mesmo vrtice.

3. Grafo hamiltoniano ou grafo de Hamilton um grafo que admite um circuito de Hamilton.

4. Grafo Bipartido

Um grafo diz-se bipartido quando o conjunto dos seus vrtices

pode ser dividido em dois subconjuntos V1 e V2 tais que qualquer

aresta do grafo une um vrtice de V1 a um vrtice de V2.

Exemplo:V1 = {A, B} V2 = {C, D, E}

5. Grafo Completo Bipartido cada um dos vrtices de uma linha

adjacente a todos os vrtices da outra linha.

Se o n de vrtices nas duas linhas igual, o grafo

hamiltoniano (admite circuitos de hamilton).

Se a diferena entre o n de vrtices das duas linhas 1, o grafo admite caminhos

mas no circuitos de Hamilton.

Se a diferena entre o n de vrtices das duas linhas superior a 1, o garfo no

admite nem caminhos nem circuitos de Hamilton

6. Num Grafo Grelha:

I. se o n de colunas e o n de linhas par, o grafo admite circuitos de Hamilton

II. se o n de colunas par e o n de linhas mpar ou se o n de colunas mpar e o n

de linhas par, o grafo admite circuitos de Hamilton

III. se o n de colunas e de linhas mpar, o grafo no admite circuitos de Hamilton.

Concluso: um grafo-grelha Hamiltoniano excepto quando o n de linhas e o n de

colunas mpar

7. Grafos Completos tm sempre circuitos de Hamilton

8. Grafos Kn (grafos completos e simples com n vrtices)

Um grafo Kn tem (n-1)! Circuitos Hamiltonianos

K4 tem ( ) 6123!3!14 === circuitosHamiltonianos. So eles:

ABCDA ACDBA ABDCA ADCBA ACBDA ADBCA

K5 tem ( ) 241234!4!15 === circuitos

Hamiltonianos so eles:

Observao: Metade dos circuitos hamiltonianos encontrados (12) so circuitos

espelhos dos restantes. Por exemplo o Circuito 24 circuito espelho do circuito 1; o

circuito 18 circuito espelho de 2, etc.

9. Num grafo kn pesado, um circuito hamiltoniano e o correspondente circuito espelho tm

o mesmo peso. Assim, nesta situao, considera-se que os dois circuitos (um circuito e o

seu circuito espelho) so iguais.

Ento, num grafo pesado Kn existem ( )2

!1n circuitos hamiltonianos distintos.

10. O Problema do Caixeiro-viajante prope encontrar, num grafo completo Kn pesado, um

circuito hamiltoniano com um custo mnimo.

Para encontrar este circuito existem vrios procedimentos algortmicos possveis:

I. Algoritmo da Fora Bruta:

1 passo: Encontrar todos os circuitos de hamilton possveis (a partir de um

determinado vrtice);

2 passo: Adicionar os pesos das arestas utilizadas em cada um dos circuitos;

3 passo Escolher o circuito para o qual a soma dos pesos das arestas percorridas

mnimo.

1. ABCDEA 9. ACDBEA 17. ADEBCA 2. ABCEDA 10. ACDEBA 18. ADECBA 3. ABDCEA 11. ACEBDA 19. AEBCDA 4. ABDECA 12. ACEDBA 20. AEBDCA 5. ABECDA 13. ADBCEA 21. AECBDA 6. ABEDCA 14. ADBECA 22. AECDBA 7. ACBDEA 15. ADCBEA 23. AEDBCA 8. ACBEDA 16. ADCEBA 24. AEDCBA

II. Algoritmo da Cidade mais Prxima (em grafos pesados Kn):

1 Passo: Definimos a cidade (vrtice) de partida.

2 Passo: Seleccionamos a cidade mais prxima tal que:

Se houver duas mesma distncia escolhemos aleatoriamente;

No podemos repetir nenhuma cidade excepto a ltima, depois de terem

sido todas visitadas, voltando ao ponto de partida.

III. Algoritmo do Peso das Arestas (em grafos pesados Kn):

1 Passo: Ordenam-se as arestas pelos seus pesos;

2 Passo: Seleccionam-se sucessivamente as arestas com menor peso, tal que:

Um vrtice nunca poder aparecer trs vezes;

Nunca se fecha um circuito havendo vrtices por visitar

3 Passo: Ordena-se a soluo conforme o vrtice de partida escolhido.

Os algoritmos cidade mais prxima e peso das arestas no garantem encontrar o circuito

hamiltoniano mnimo (o ptimo), garantindo apenas encontrar um dos melhores. Mesmo no

obtendo o circuito ptimo, a aplicabilidade destes dois algoritmos fcil, rpida e rentvel.

Com o algoritmo da fora bruta encontra-se o circuito hamiltoniano mnimo, o ptimo, mas ao

contrrio dos outros de aplicabilidade difcil e moroso, sendo mesmo impossvel, na maioria

dos casos, de aplic-lo sem recorrer aos computadores. Assim, mais vantajoso utilizar os

algoritmos da cidade mais prxima e o do peso das arestas, apesar de no termos a certeza

de encontrarmos o circuito hamiltoniano mnimo.