Caminhos e ciclos hamiltonianos

• Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo, não repetindo nenhum. • Se o caminho hamiltoniano começa e termina no mesmo vértice, temos um ciclo hamiltoniano. • Um grafo que contém um ciclo hamiltoniano é um grafo hamiltoniano

Ciclo Hamiltoniano:

Caminho Hamiltoniano:

• 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" passando por todas as cidades exatamente uma vez, com a restrição de que só fosse possível viajar de uma cidade a outra se existisse uma aresta entre os vértices correspondentes.

• Um problema que envolve caminhos hamiltonianos é o problema do caixeiro viajante, em que um caixeiro deseja visitar um conjunto de N cidades (vértices), passando por cada cidade exatamente uma vez e retornando à cidade de origem, fazendo o caminho de menor tamanho possível.

• 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?

• Problema do Cavalo A solução deste problema passa por verificar se o grafo G é hamiltoniano. Este grafo tem 64 vértices e 168 arestas, e, em realidade, contém vários ciclos hamiltonianos, um os quais é apresentado na figura que se segue, lembrando que não importa a posição inicial do Cavalo.

• Porém, caso o tabuleiro seja um NxN onde N é um número ímpar, não teremos um ciclo hamiltoniano.

1. Qualquer ciclo hamiltoniano pode ser convertido para um caminho Hamiltoniano, removendo-se uma de suas arestas, mas um caminho Hamiltoniano só pode ser estendido para um ciclo