Caminhos e ciclos hamiltonianos

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (816 palavras )
  • Download(s) : 0
  • Publicado : 8 de abril de 2012
Ler documento completo
Amostra do texto
• 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 ciclohamiltoniano. • 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 SirWilliam 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 como 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 deuma 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 desejavisitar 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 ojogo 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 cicloshamiltonianos, 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 ciclohamiltoniano.

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...
tracking img