Um grafo
G é
dito ser hamiltoniano se existe um ciclo em G
que contenha todos os seus vértices,
sendo que cada vértice só aparece uma vez
no ciclo. Este ciclo é chamado de ciclo
hamiltoniano. Sendo
assim. um grafo é
hamiltoniano se ele
contiver um ciclo hamiltoniano.
A
título de exemplo, considere os grafos G1
e G2
ao lado. É fácil notar que G1
contém o ciclo (v1,
v2,
v3,
v4,
v5,
v1)
que é hamiltoniano. Logo, G1
é um grafo hamiltoniano. O mesmo não
acontece com G2
.
O
adjetivo "hamiltoniano" deve-se ao
matemático irlandês Sir William Rowan
Hamilton (1805-1865). Diz-se que ele inventou
um jogo que envolve um dodecaedro (sólido
regular com 20 vértices, 30 arestas e 12
faces). Hamilton rotulou cada vértice do
dodecaedro com o nome de uma cidade
conhecida. O objetivo do jogo era que o
jogador viajasse "ao redor do
mundo" ao determinar uma viagem circular
que incluísse todas as cidades extamente uma
vez, com a restrição de que só fosse
possível viajar de uma cidade a outro se
existisse uma aresta entre os vértices
correspondentes. A figura ao lado mostra um
grafo que representa este problema, ou seja
os vértices e arestas de um dodecaedro.
Não
se dispõe de um método conveniente para
determinar se um grafo é Hamiltoniano. Há
diversos teoremas específicos para
determinados tipos de grafos, os quais
fornecem condições que são, na maior parte
dos casos, suficientes, porém não
necessárias. É o caso de:
Teorema:
Se G
é um grafo de ordem p (>=3) tal que o
grau(v) >= p/2 para cada vértice v de
G, então G é hamiltoniano.
Esta
condição é suficiente para garantir que um
grafo G
seja hamiltoniano, mas certamente ela não é
necessária. Por exemplo, G
pode ser simplesmente um ciclo, caso em que
cada vértice tem exatamente grau dois, e
ainda assim ser hamiltoniano.
Problema
do Caixeiro Viajante
Suponha
que a área de venda de um caixeiro
viajante inclua várias cidades, muitas
das quais, aos pares, estão conectadas
por rodovias. O trabalho do caixeiro
requer que ele visite cada cidade
pessoalmente. Sob que condições seria
possível que ele estabelecer uma viagem
circular (que o leve ao ponto de partida)
de forma a que ele visite cada cidade
exatamente uma vez?
Este
problema pode ser modelado por um grafo G(V,A),
onde:
V = { c | c
é uma cidade}
A = { (c1,c2)
| há uma estrada que conecta as
cidades c1
e c2,
sendo que ela não passa por nenhuma
outra cidade neste trajeto}
Modelado
desta forma, a solução deste problema
passa por verificar se o grafo G
é hamiltoniano.
Considere
o jogo de xadrez. Seguindo as regras de
movimento do cavalo, é possível
que um cavalo parta de uma casa
qualquer, percorra todo o tabuleiro
visitando cada casa uma e somente uma
única vez e retorne à casa inicial ?
O
Problema da Coleta de Correspondências
A
Empresa Brasileira de Correios e
Telégrafos mantém vários postos de
coleta de correspondência espalhados
pela cidade, inclusive em bairros mais
afastados. A localização e a quantidade
destes postos são por vezes modificados
de forma que diariamente o motorista
responsável por recolher a
correspondência recebe um esquema que
mostra o melhor percursso para passar em
todos os postos de coleta. Este esquema
é montado manualmente por um
funcionário da E.C.T.. Este funcionário
não aguenta mais as reclamações dos
motoristas de que as rotas que ele traça
nunca são as melhores e pede demissão.
O chefe, sem saber como tratar o
problema, resolve contratar um
especialista (você), para resolvê-lo.
Como você modelaria o problema? Como
encontrar a melhor rota? Que
particularidades devem ser tratadas?