| Procura | Nós | Resultado |
|---|---|---|
| Retrocesso simples | – | – |
| Ordem de Warnsdorff | – | – |
| Verificações de beco e conexidade | – | – |
| As três | – | – |
Explorador de caminhos hamiltonianos
Em 1857 William Rowan Hamilton inventou um quebra-cabeças: percorrer as arestas de um dodecaedro passando por cada um dos seus 20 cantos exatamente uma vez e terminar onde começou. Uma rota assim chama-se hoje ciclo hamiltoniano. É fácil de verificar e, em geral, difícil de encontrar. Trace uma você mesmo no dodecaedro de Hamilton, num tabuleiro de xadrez ou num grafo que desenhe, ou veja uma procura com retrocesso à caça de uma, conte os becos sem saída em que cai e veja quanto umas poucas verificações simples encurtam a procura. Escolha um grafo e um objetivo: um ciclo que volta ao início ou um caminho. Traçar: clique num vértice para começar e depois num vizinho de cada vez; os anéis tracejados mostram para onde pode ir. Um clique no último vértice, Voltar ou Desfazer recua um passo, e Dica indica um próximo passo que ainda chega ao fim. Procura: com Iniciar ou Passo corre uma procura com retrocesso, que acrescenta vértices até ficar presa e então volta atrás; os tracejados vermelhos mostram os recuos e as barras contam os nós por comprimento de caminho. Antes do início, um clique num vértice escolhe onde ela começa. As caixas ligam e desligam a poda, Comparar corre a mesma procura com e sem ela, e Contar todos conta cada ciclo ou caminho de um grafo pequeno. Editar: clique para acrescentar um vértice, clique em dois vértices para os ligar ou separar, arraste para mover um, e Eliminar retira o vértice selecionado.
Como funciona
- Escolha um grafo, como o dodecaedro de Hamilton, o grafo de Petersen ou um passeio do cavalo, ou desenhe o seu em Editar, e escolha como objetivo um ciclo ou um caminho.
- Em Traçar, clique num vértice para começar e depois num vizinho após outro. Voltar e Desfazer recuam um passo, e Dica mostra um próximo passo que ainda chega ao fim.
- Em Procura, carregue em Iniciar ou Passo para ver o retrocesso à procura de uma rota, ligue e desligue a poda, e carregue em Comparar para ver quantos nós cada versão precisa.
Hamilton contra Euler
Um caminho euleriano usa cada aresta uma vez; um caminho hamiltoniano passa por cada vértice uma vez. Parecem semelhantes mas comportam-se de forma muito diferente. Saber se um grafo conexo tem um caminho euleriano decide-se contando os vértices de grau ímpar, como Euler mostrou em 1736: tem um quando não há nenhum ou há dois. Para caminhos hamiltonianos não se conhece regra semelhante. Decidir se um grafo tem um ciclo hamiltoniano é NP-completo, um dos 21 problemas da lista de Richard Karp de 1972, por isso um método rápido para ele daria métodos rápidos para milhares de outros problemas difíceis. O que existe são condições que decidem alguns grafos. O teorema de Dirac de 1952 garante um ciclo hamiltoniano quando cada vértice tem grau pelo menos n/2, e o de Ore de 1960 quando dois vértices não ligados têm sempre graus que somam pelo menos n; um vértice de grau 1, um vértice de corte ou duas classes de cor de tamanhos diferentes excluem-no.
Como funciona a procura
O retrocesso constrói o caminho um vértice de cada vez e, quando fica preso, desfaz o último passo e tenta o vizinho seguinte. Encontra sempre um ciclo hamiltoniano se houver um, mas o número de caminhos parciais pode crescer exponencialmente. Na grelha 5 × 5, que não tem ciclo hamiltoniano, o retrocesso simples explora 153.745 nós antes de ter a certeza. Duas verificações param cedo os caminhos sem esperança: um vértice não visitado com menos de dois vizinhos livres já não cabe num ciclo, e quando os vértices não visitados se separam em partes distintas, nenhum caminho único os pode cobrir. Com ambas, a mesma prova leva 1.761 nós. A regra de Warnsdorff de 1823, que tenta primeiro o vizinho com menos jogadas seguintes, encontra um passeio do cavalo em 8 × 8 a partir de um canto em 64 jogadas sem um único beco sem saída.
Perguntas frequentes
Qual é a diferença entre um caminho hamiltoniano e um ciclo hamiltoniano?
Um caminho hamiltoniano passa por cada vértice de um grafo exatamente uma vez. Um ciclo hamiltoniano faz o mesmo e depois volta por mais uma aresta ao ponto de partida, por isso pode começar em qualquer um dos seus vértices. Todo grafo com um ciclo hamiltoniano tem um caminho hamiltoniano (retire uma aresta do ciclo), mas não o contrário: o grafo de Petersen tem caminhos hamiltonianos e nenhum ciclo hamiltoniano.
O dodecaedro tem um ciclo hamiltoniano?
Sim, 30, contando cada ciclo uma vez, seja qual for o início e o sentido. Hamilton transformou isso no jogo icosiano em 1857, um tabuleiro com os 20 cantos de um dodecaedro achatado marcados com consoantes, e vendeu os direitos por 25 libras ao fabricante de brinquedos londrino John Jaques and Son. Contar todos encontra os 30 ciclos em cerca de 1.400 nós.
Porque é que uma grelha 5 × 5 não tem ciclo hamiltoniano?
Pinte os 25 pontos como um tabuleiro de xadrez: 13 ficam com uma cor e 12 com a outra, e cada passo vai para a outra cor. Um ciclo alterna as cores por toda a volta, por isso precisa de tantos de uma como da outra, o que 13 e 12 não dão. O mesmo argumento vale para toda grelha com um número ímpar de pontos, para um cavalo num tabuleiro 5 × 5 ou 7 × 7 (o cavalo muda sempre de cor de casa) e para o grafo de Herschel, cujas duas classes têm 6 e 5 vértices. Um caminho hamiltoniano continua possível: começa e termina na cor mais numerosa.
Como é que a regra de Warnsdorff encontra um passeio do cavalo?
H. C. von Warnsdorff propôs em 1823 mover sempre o cavalo para a casa a partir da qual terá menos jogadas seguintes. As casas junto às bordas e aos cantos, fáceis de isolar, são assim visitadas cedo, enquanto o cavalo ainda lá consegue entrar. A regra é prática, não uma garantia, e os empates têm de ser desfeitos de algum modo, mas num tabuleiro 8 × 8 costuma completar um passeio sem voltar atrás. Unida ao retrocesso, como nesta aplicação, encontra passeios abertos a partir de 5 × 5 e passeios fechados nos tabuleiros 6 × 6 e 8 × 8.
Quantos ciclos hamiltonianos tem um grafo completo?
(n − 1)!/2 para n ≥ 3. Fixe o vértice de partida; os outros n − 1 podem seguir em qualquer ordem, e cada ciclo é contado duas vezes, uma por sentido. K₆ tem 5!/2 = 60 e K₁₀ tem 181.440. São as voltas entre as quais um caixeiro-viajante tem de escolher, e é por isso que tentá-las todas deixa de ser possível tão depressa.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor