Um caminho hamiltoniano num grafo e umcaminho onde ocorrem todos os vertices dografo exactamente uma vez. Analogamente,um ciclo hamiltoniano e um ciclo que contemtodos os vertices do grafo exactamente umavez, com excepccao dos vertices inicial e fi-nal que tem de coincidir. Um grafo diz-sehamiltoniano se possuir algum ciclo hamil-toniano.

Se retirarmos a ultima aresta a um ciclo ha-miltoniano obtemos um caminho hamiltoni-ano, logo todo o grafo hamiltoniano pos-sui caminhos hamiltonianos. No entanto, orecıproco desta afirmacao nao e verdadeiro,como o seguinte exemplo mostra.

Exemplo.

1

A designacao de hamiltoniano refere-se ao matematico irlandes Sir William RowanHamilton (1805–1865), famoso pela sua de-soberta dos quaternioes, uma generalizacaonao-comutativa dos numeros complexos. Porvolta de 1857 Hamilton criou um jogo ao qualdeu o nome de jogo icosiano, aludindo aos 20vertices do dodecaedro.

A cada um desses vertices era atribuıdoo nome de uma capital e o objectivo do jogoera, usando as arestas do dodecaedro, pla-near um percurso que visitasse cada uma dascidades exactamente uma vez e terminassena cidade de onde se tinha partido. Assim,procurava-se um ciclo hamiltoniano no grafodo dodecaedro. Um exemplo de um tal cicloe o seguinte:

2

3

4

Exemplo. Este exemplo mostra a independenciaentre a existencia de circuitos (atalhos) eu-lerianos e a existencia de ciclos (caminhos)hamiltonianos num grafo.

circ euler atalh euler cic ham cam ham(a) sim nao sim sim(b) nao sim nao sim(c) nao nao sim sim(d) sim nao nao sim(e) nao sim nao nao(f) nao nao nao sim

5

Exemplo. O grafo G abaixo nao e Hamil-toniano porque a aresta a indicada e umaponte. O grafo H tambem nao e Hamilto-niano porque se v for o vertice indicado nafigura entao !(H � v) = 2 > 1. No entanto,basta acrescentar uma qualquer aresta entrevertices nao adjacentes a G ou H para que orespectivo grafo se torne Hamiltoniano. Poresta razao, dizemos que G e H sao ambosgrafos nao-Hamiltonianos maximais.

a

Gv H

6

Exemplo. Se retirarmos os tres vertices re-presentados a preto no grafo G abaixo, obte-mos um grafo com 4 componentes conexas.Logo G nao e Hamiltoniano.

7

Algoritmo

Seja G um grafo simples com n � 3 verticesque satisfaz as hipoteses do Teorema de Ore.

Passo 1. Escolher um vertice qualquer de G

e, acrescentando vertices adjacentes a direitae a esquerda, construir um caminho abertoem G de comprimento cada vez maior, atenao ser possıvel prosseguir, digamos

C = y1 � y2 � · · ·� ym, 3 m n,

de comprimento m� 1.

Passo 2.

(i) Se y1 e ym nao forem adjacentes em G,prosseguimos para o Passo 3. Caso contrario,y1 e ym sao adjacentes e prosseguimospara (ii).

8

(ii) Se m = n entao y1 � y2 � · · · � ym � y1 eum ciclo Hamiltoniano em G; parar. Casocontrario, y1 e ym sao adjacentes e m <n; ir para (iii).

(iii) Existe um vertice z, diferente de y1, . . . , ym,que e adjacente a yk, para algum 1 k m. Substituir C pelo caminho aberto decomprimento m

z � yk � yk+1 � · · ·� ym � y1 � · · ·� yk�1.

De seguida, estender C acrescentando verticesadjacentes a direita e a esquerda ate naoser possıvel prosseguir, de forma a ter-mos ainda um caminho aberto de com-primento maior ou igual a m. Voltar aoinıcio do Passo 2.

Passo 3. Encontrar um vertice yk, com 1 <k < m, tal que y1 e adjacente a yk e ym eadjacente a yk�1. Substituir C pelo caminho

y1 � · · ·� yk�1 � ym � ym�1 � · · ·� yk.

de comprimento m�1, tal como C. As duasextremidades deste caminho sao adjacentes.Voltar ao Passo 2(ii).

Teorema 1 (Dirac, 1952). Se o grafo Gtem n vertices (n � 3) e d(v) � n/2 para todo

o vertice v de G, entao G e hamiltoniano.

Exemplo. O grafo seguinte e hamiltoniano:

Note-se que a condicao do Teorema de Dirace suficiente mas nao e necessaria. Por exem-plo, o ciclo de cinco vertices C5 e hamiltoni-ano mas nenhum dos seus vertices satisfaz acondicao d(v) � 5/2.

A prova do Teorema de Dirac pode ser adap-tada para uma prova do seguinte resultadomais geral:Teorema 2. Seja G um grafo com n vertices

e sejam u e v vertices nao adjacentes de Gtais que

d(u) + d(v) � n.

Seja G + uv o grafo obtido adicionando a

aresta uv a G. Entao G e hamiltoniano se

e so se G + uv e hamiltoniano.

9

Exemplo. Aplicacoes sucessivas do teoremaanterior permitem chegar ao grafo hamilto-niano completo K6, logo G e tambem hamil-toniano.

10

Exemplo. Aplicar o algoritmo baseado noTeorema de Ore ao seguinte grafo:

11

O Problema do Caixeiro Viajante

Exemplo. (Ze Pedro, o caixeiro viajante) OZe Pedro e um caixeiro viajante que tem cli-entes em cinco cidades, que abreviamos porA, B, C, D e E. Ele precisa de planear umaviajem de negocios com cidade de partida ede destino final A (a cidade onde mora), emque passara por cada uma das restantes qua-tro cidades precisamente uma vez. O grafoabaixo representa o custo de cada viagem(ida ou volta) entre cada par de cidades.

Qual o percurso mais barato para esta via-gem do Ze Pedro? Por outras palavras, quale o ciclo hamiltoniano optimal (isto e, cujasoma do peso das arestas e menor) no grafodado?

12

Exemplo. (As Luas de Jupiter e Saturno)

No ano 2020 sera lancada da Terra uma ex-pedicao para explorar as luas de Jupiter e Sa-turno. Serao visitadas Callisto, Ganymede, Io(luas de Jupiter), Mimas e Titan (luas de Sa-turno), onde serao recolhidas amostras comas quais a expedicao voltara a Terra. A se-guinte figura indica a duracao da missao (emanos) entre cada par de luas. Qual e o ciclohamiltoniano optimal (mais breve) no graforepresentado?

(Terra)

13

Exemplo. (Vida em Marte) A tabela abaixoindica as distancias aproximadas (em milhas)entre sete locais de Marte, onde cientistas daNASA pensam poder encontrar vestıgios devida com maior probabilidade.

A G H I N P WA - 7500 5000 2800 3500 1500 2200G 7500 - 3000 6000 8000 6500 5000H 5000 3000 - 4000 4800 3500 2800I 2800 6000 4000 - 2000 3000 2900N 3500 8000 4800 2000 - 4000 3200P 1500 6500 3500 3000 4000 - 1300W 2200 5000 2800 2900 3200 1300 -

Quer-se planear uma viagem que colocaraum robot em Marte, aterrando em A. Orobot devera percorrer cada um dos locais,recolher amostras de solo e regressar a A,de onde um fogetao trara as amostras paraTerra de forma a serem analisadas.

Qual sera o ciclo hamiltoniano optimal nografo correspondente?

14

Metodo Exaustivo

Este metodo consiste em fazer uma lista detodos os ciclos hamiltonianos do grafo, cal-cular o peso de cada um e escolher um depeso mınimo.

Quantos ciclos hamiltonianos e que exis-

tem no grafo completo de n vertices Kn?

15

Exemplo. (Ze Pedro, o caixeiro viajante)

Uma forma de resolver o problema do Ze Pe-dro e usar o metodo de exaustao em que secalculam os pesos dos 4! = 24 ciclos hamil-tonianos possıveis em K5:

ciclo hamilt custo total ciclo inversoABCDEA 185+121+174+199+133=812 AEDCBAABCEDA 185+121+120+199+152=777 ADECBAABDCEA 185+150+174+120+133=762 AECDBAABDECA 185+150+199+120+119=773 ACEDBAABECDA 185+200+120+174+152=831 ADCEBAABEDCA 185+200+199+174+119=877 ACDEBAACBDEA 119+121+150+199+133=722 AEDBCAACBEDA 119+121+200+199+152=791 ADEBCAACDBEA 119+174+150+200+133=776 AEBDCAACEBDA 119+120+200+150+152=741 ADBECAADBCEA 152+150+121+120+133=676 AECBDAADCBEA 152+174+121+200+133=780 AEBCDA

Verificamos assim que ha exactamente doisciclos optimais, o ciclo ADBCEA e o seu in-verso, o ciclo AECBDA. Em qualquer doscasos, o Ze Pedro gasta 676 Euros na suaviagem de trabalho e esta e a melhor solucao.

16

Metodo do Vizinho Mais Proximo

Escolhe-se um vertice e a aresta de menorpeso incidente nesse vertice. Esta aresta de-termina um outro vertice. De cada novovertice escolhe-se a aresta de menor peso,de entre as arestas que sao incidentes nessevertice e num vertice que ainda nao foi esco-lhido. No final, regressa-se ao vertice inicial.

Exemplo. (Ze Pedro, o caixeiro viajante)

No caso do Ze Pedro, por este algoritmo elecomeca pelo vertice A. De A vai para C, deC para E, depois para D e finalmente paraB, de onde regressa a A.

O custo desta viagem e de 773 Euros. Ometodo do vizinho mais proximo e muito maisrapido do que que o metodo de exaustao,embora nao produza, em geral, uma solucaooptimal. Neste caso, o custo adicional e de97 Euros, e o erro relativo e de 97/676 '14,3%.

17

Exemplo. (Ze Pedro, o caixeiro viajante)

Suponhamos que o Ze Pedro consegue alar-gar o seu negocio e ter um leque de clien-tes espalhados por dez cidades. O custo dasviagens entre as cidades esta representadoabaixo, em forma de um grafo e de uma ta-bela:

Neste caso, para usar o metodo exaustivo te-mos de calcular o peso de 9! = 362880 cicloshamiltonianos. Demorando 30 segundos porcada um dos ciclos demorarıamos 3024 ho-ras, o que e mais de 4 meses a trabalhar 24horas por dia, 7 dias por semana!

Tentemos entao o metodo do vizinho maisproximo. O ciclo que obtemos e

ACEDBJGKFHA,

cujo custo e de 2153 Euros.18

Metodo do Vizinho Mais Proximo com

Repeticao

Exemplo. (Ze Pedro, o caixeiro viajante)

Voltando mais uma vez ao exemplo do Ze Pe-dro e aplicando o algoritmo do vizinho maisproximo com repeticao, obtemos sucessiva-mente os ciclos:

ciclo custo em EurosACEDBA 773BCAEDB 722CAEDBC 722DBCAED 722ECADBE 741

Assim, este algoritmo escolhe o ciclo BCAEDB =CAEDBC = DBCAED, cujo custo e de 722Euros. Como sabemos, este nao e um ciclooptimal, mas o resultado e mais satisfatoriodo que o obtido usando o algoritmo do vizi-nho mais proximo (sem repeticao) comecandoem A.

19

Metodo do Elo Mais Barato

Comecamos por escolher a aresta de menorpeso do grafo. Depois, escolhemos a arestade menor peso de entre as arestas que naoforam ainda escolhidas (que nao tem de seradjacente a primeira), sujeitos as seguintesregras:

1. nao permitir que se forme um ciclo a naoser que ja todos os vertices sejam inciden-tes com alguma das arestas ja escolhidas;

2. nao permitir que de entre as arestas es-colhidas haja tres incidentes no mesmovertice.

Repetimos este processo ate obtermos umciclo, que sera necessariamente um ciclo ha-miltoniano. Se alguma destas duas regrasfosse violada nao obeterıamos um ciclo ha-miltoniano. Reciprocamente, se seguirmosestas regras terminamos com um ciclo ha-miltoniano.

20

Exemplo. (Ze Pedro, o caixeiro viajante)

Usemos este algoritmo no problema do ZePedro com cinco cidades.

Obtemos o ciclo ACEBDA, de peso 741 Eu-ros.

21

Exemplo. (Vida em Marte) Retomemos oproblema do robot a recolher amostras desolo em Marte apresentado no inıcio. Vamosaplicar-lhe os algoritmos que acabamos dediscutir:

Metodo exaustivo. Temos de calcular opeso de 6! = 720 ciclos hamiltonianos. Usandoum computador obtemos um ciclo optimal de20100 milhas.

Metodo do elo mais barato. Obtemos ociclo APWHGNIA, de peso 21400 milhas.

Metodo do vizinho mais proximo. Comecandoem A, obtemos o ciclo APWHGINA, de peso20100 milhas.

Metodo do vizinho mais proximo com re-

peticao. Uma vez que comecando em A ob-tivemos um ciclo optimal, este metodo pro-duzira uma solucao com o mesmo peso.

22