Grafos Hamiltonianos

 

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.

Problema do Cavalo

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?