Caminhos e ciclos hamiltonianos explicados

Desenhe cinco pontos em círculo, ligue cada um aos seus dois vizinhos, e pode dar a volta passando uma vez por cada ponto e voltar a casa: um ciclo hamiltoniano. Acrescente umas arestas ou retire algumas e a pergunta torna-se surpreendentemente difícil. Saber se um grafo tem um ciclo assim é um dos problemas mais conhecidos a que nenhum computador sabe ainda responder depressa para todo grafo.

Um dodecaedro achatado com os seus 20 cantos marcados com consoantes e um ciclo hamiltoniano que passa por todos traçado numa linha clara, com uma aresta vermelha tracejada onde uma procura voltou atrás
Um dodecaedro achatado com os seus 20 cantos marcados com consoantes e um ciclo hamiltoniano que passa por todos traçado numa linha clara, com uma aresta vermelha tracejada onde uma procura voltou atrás

Cada vértice uma vez

Um grafo é um conjunto de pontos, os vértices, ligados por linhas, as arestas. Um caminho hamiltoniano segue arestas e passa por cada vértice exatamente uma vez; um ciclo hamiltoniano volta ainda ao ponto de partida, por isso tem tantas arestas como vértices. Um grafo com um ciclo hamiltoniano chama-se hamiltoniano. Verificar uma rota proposta é fácil: conte os vértices e olhe para cada passo. Encontrar uma, ou provar que não há nenhuma, é a parte difícil, porque o número de ordens em que os vértices poderiam ser visitados cresce como n!, já 2,4 × 10¹⁸ para 20 vértices.

O jogo icosiano de Hamilton

William Rowan Hamilton, o matemático irlandês que descobriu os quaterniões, inventou o jogo icosiano em 1857. O seu tabuleiro mostrava um dodecaedro achatado no plano, com os 20 cantos marcados por consoantes, e a tarefa principal era pôr pinos numerados de 1 a 20 nos cantos de modo que números consecutivos, e 20 e 1, ficassem ligados por arestas. Hamilton vendeu os direitos por 25 libras ao fabricante de brinquedos londrino John Jaques and Son, que o lançou em 1859; vendeu mal. O quebra-cabeças tem 30 soluções, contando um ciclo uma vez, seja qual for o início e o sentido. A pergunta em si não era nova: Thomas Kirkman perguntara que poliedros têm um ciclo por todos os seus cantos num artigo enviado à Royal Society em 1855, e mostrara um que não tem.

Passeios do cavalo

Um passeio do cavalo move um cavalo de xadrez de modo que pouse em cada casa exatamente uma vez: um caminho hamiltoniano no grafo cujos vértices são as casas e cujas arestas são as jogadas do cavalo. Um passeio fechado termina a um salto de cavalo do início, ou seja, um ciclo hamiltoniano. Os jogadores de xadrez punham estes problemas há mais de mil anos, e Euler estudou-os num artigo de 1759. Em 1823 H. C. von Warnsdorff propôs ir sempre para a casa com menos jogadas seguintes; esta regra simples costuma completar um passeio de um tabuleiro 8 × 8 sem voltar atrás. O cavalo muda sempre de cor de casa, por isso um passeio fechado precisa de tantas casas claras como escuras, o que exclui os tabuleiros com um número ímpar de casas. Allen Schwenk mostrou em 1991 exatamente que tabuleiros retangulares têm um passeio fechado; entre os quadrados, todos os de lado par a partir de 6. O tabuleiro de xadrez comum tem 13.267.364.410.532 passeios fechados, contados por Brendan McKay em 1997.

Grafos sem ciclo hamiltoniano

As provas mais rápidas de que não há ciclo são argumentos de contagem. Se os vértices puderem ser pintados com duas cores de modo que cada aresta ligue cores diferentes, um ciclo alterna e precisa de tantos vértices de cada cor; uma grelha 5 × 5 tem 13 de uma e 12 da outra, por isso não tem ciclo hamiltoniano. Um vértice de corte, cuja remoção parte o grafo, teria de ser atravessado duas vezes, e um vértice de grau 1 não pode ser atravessado de todo. Alguns grafos escapam a todos esses argumentos. O grafo de Petersen, publicado por Julius Petersen em 1898, tem 10 vértices de grau 3 e nenhum ciclo hamiltoniano, e no entanto apagar um vértice qualquer deixa um grafo que tem um; é o menor grafo hipo-hamiltoniano. O grafo de Herschel, com o nome de Alexander Stewart Herschel, que escreveu sobre o jogo icosiano em 1862, tem 11 vértices e 18 arestas e é o grafo de um poliedro com nove faces quadrangulares. Nenhum poliedro com menos cantos fica sem ciclo hamiltoniano. Em 1884 Peter Guthrie Tait conjeturou que todo poliedro com três arestas em cada canto tem um; W. T. Tutte encontrou um contraexemplo com 46 vértices em 1946.

Condições que garantem um

Se um grafo tem muitas arestas, um ciclo hamiltoniano é certo. Gabriel Dirac provou em 1952 que um grafo com n ≥ 3 vértices em que cada vértice tem grau pelo menos n/2 tem um, e Øystein Ore enfraqueceu a condição em 1960: basta que dois vértices não ligados tenham sempre graus que somem pelo menos n. Ambas as condições valem num só sentido. Um simples anel de 100 vértices tem grau 2 em toda a parte, muito abaixo de 50, e é mesmo assim um ciclo hamiltoniano. É este o panorama geral: há condições suficientes e há razões de falha, e pelo meio estende-se um vasto território de grafos que só uma procura pode decidir.

Porque não se conhece um teste rápido

Decidir se um grafo tem um ciclo hamiltoniano é NP-completo; foi um dos 21 problemas da lista de Richard Karp de 1972. Um método que o resolvesse depressa para todo grafo resolveria depressa milhares de outros problemas e decidiria a questão P contra NP. O contraste com os caminhos eulerianos, que usam cada aresta uma vez, é notável: Euler mostrou em 1736 que contar os vértices de grau ímpar decide essa pergunta de imediato. Os melhores métodos exatos para ciclos hamiltonianos continuam a levar tempo exponencial. A programação dinâmica sobre todos os subconjuntos de vértices, encontrada por Richard Bellman e por Michael Held e Richard Karp em 1962, precisa de cerca de n² × 2ⁿ passos, e o método aleatorizado de Andreas Björklund de 2010 de cerca de 1,657ⁿ. Na prática o retrocesso com boa poda lida com grafos de algumas dezenas de vértices, e o problema do caixeiro-viajante, que procura o ciclo hamiltoniano mais curto, é a versão com pesos da mesma pergunta.

Códigos de Gray e o hipercubo

Escreva os números de 0 a 7 como códigos de 3 bits e ligue dois códigos quando diferem exatamente num bit: o resultado é o grafo de um cubo. Um ciclo hamiltoniano que o percorre, por exemplo 000, 001, 011, 010, 110, 111, 101, 100, lista os oito códigos de modo que cada um difere do anterior num único bit. Uma lista assim é um código de Gray, com o nome de Frank Gray dos Bell Labs, que o descreveu numa patente depositada em 1947. Todo hipercubo tem um: escreva os códigos com menos um bit, depois a mesma lista ao contrário, e ponha um 0 à frente da primeira metade e um 1 à frente da segunda. Os codificadores rotativos usam códigos de Gray para que uma leitura feita entre duas posições nunca esteja errada por mais de um passo. O cubo tem 6 ciclos hamiltonianos e o hipercubo de 4 bits tem 1.344.

Explore

Abra o explorador de caminhos hamiltonianos para tentar você mesmo o quebra-cabeças de Hamilton, com anéis tracejados a mostrar para onde pode ir, ou mude para Procura e veja o retrocesso a trabalhar: o caminho cresce, tracejados vermelhos marcam onde volta atrás, e as barras contam os nós por comprimento de caminho. Ligue e desligue a verificação de becos, a de conexidade e a ordem de Warnsdorff, compare quantos nós cada uma precisa, conte todos os ciclos de um grafo pequeno, ou desenhe o seu próprio grafo e veja quais dos testes rápidos se aplicam.

Perguntas frequentes

Um grafo com um circuito euleriano é também hamiltoniano, ou o contrário?

Nenhum decorre do outro. O laço, dois triângulos com um vértice comum, tem um circuito euleriano porque todos os graus são pares, mas nenhum ciclo hamiltoniano, já que o vértice comum teria de ser atravessado duas vezes. O grafo completo K₄ tem ciclos hamiltonianos, mas os quatro vértices têm grau 3, por isso não tem circuito euleriano.

Um computador não pode simplesmente tentar todas as ordens?

Só em grafos pequenos. Há n! ordens de n vértices, cerca de 2,4 × 10¹⁸ para 20. O retrocesso faz muito melhor, porque só segue arestas e desiste de um caminho parcial assim que fica preso: encontra os 30 ciclos do dodecaedro de 20 vértices em cerca de 1.400 passos. Mas em alguns grafos o número de caminhos parciais cresce mesmo assim exponencialmente, e não se conhece nenhum método que evite isso para todo grafo.

O problema do caminho hamiltoniano é mais fácil do que o do ciclo?

Não, ambos são NP-completos. Cada um reduz-se ao outro: acrescente um vértice novo ligado a todos os antigos, e o grafo antigo tem um caminho hamiltoniano exatamente quando o novo tem um ciclo hamiltoniano. No outro sentido, um problema de ciclo passa a ser de caminho acrescentando uma cópia de um vértice, com os mesmos vizinhos, e um novo vértice terminal ligado ao vértice e outro à sua cópia.

Porque é que um passeio do cavalo num tabuleiro 5 × 5 tem de começar na cor dos cantos?

Das 25 casas, 13 têm a cor dos cantos e 12 a outra, e o cavalo muda de cor a cada jogada. Um passeio de 25 casas alterna as cores, por isso começa e termina na cor que tem mais casas. A aplicação encontra todos os 1.728 passeios abertos do tabuleiro 5 × 5, 864 se um passeio e o seu inverso contarem como um, e todos começam e terminam numa casa da cor dos cantos.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir o explorador de caminhos hamiltonianos