Euler's Eyes
2026-10-27
O jogo icosiano e os ciclos hamiltonianos
Em 1856, ainda às voltas com álgebras não comutativas, Hamilton inventou o cálculo icosiano: três símbolos $\iota$, $\kappa$ e $\lambda$, que obedecem às regras
$$\iota^2 = 1, \qquad \kappa^3 = 1, \qquad \lambda^5 = 1, \qquad \lambda = \iota\kappa.$$Hoje diríamos que são geradores do grupo das rotações do icosaedro, o sólido de vinte faces triangulares. Hamilton apresentou o cálculo num encontro da British Association em Dublin, em 1857, e percebeu que ele descrevia caminhos ao longo das arestas do dodecaedro, o sólido de doze faces pentagonais e vinte vértices.
O quebra-cabeça
Para tornar a ideia popular, Hamilton desenhou o dodecaedro achatado num tabuleiro, com vinte furos nos vértices, cada um com o nome de uma cidade, e vinte pinos numerados. O desafio: partir de uma cidade, visitar todas as outras exatamente uma vez, andando só pelas arestas, e voltar ao ponto de partida. Em 1859 vendeu os direitos ao fabricante de jogos John Jaques and Son, de Londres, por 25 libras. O jogo, vendido como The Icosian Game e numa versão de bolso chamada The Traveller’s Dodecahedron, foi um fracasso comercial: com um pouco de paciência, o desafio básico se resolve em minutos.
Experimente. As letras são as consoantes que Hamilton usou para nomear as cidades:
Euler resolve, Hamilton não
Um percurso que passa uma vez por cada vértice e volta ao início é hoje chamado ciclo hamiltoniano. A pergunta parece prima da das pontes de Königsberg, em que Euler queria passar uma vez por cada aresta. Mas as duas são muito diferentes. Para as arestas, Euler deu em 1736 um critério simples: basta olhar quantas arestas saem de cada vértice. Para os vértices, ninguém conhece critério simples. Em 1972, Richard Karp incluiu o problema do ciclo hamiltoniano na sua lista de problemas NP-completos: se alguém achar um método rápido para ele, terá um método rápido para milhares de outros problemas difíceis, e ganhará um milhão de dólares do Instituto Clay.
O parente mais famoso é o problema do caixeiro-viajante: entre todos os ciclos hamiltonianos de um mapa, qual é o mais curto? Ele aparece no roteiro de entregas, na perfuração de placas de circuito e no sequenciamento de DNA.
Conferir um caminho é diferente de encontrá-lo
Para verificar uma solução, basta conferir que todos os vértices aparecem uma vez, que cada par consecutivo está ligado por uma aresta e que o último se liga ao primeiro. No cubo ilustrado abaixo, verificar uma aresta equivale a comparar dois rótulos e confirmar que diferem em um único bit.
A dificuldade computacional está em encontrar uma sequência válida num grafo qualquer, ou provar que ela não existe. Uma tentativa direta, fixando o vértice inicial, pode examinar até $(n-1)!$ ordens de visita antes de descartar as que usam ligações inexistentes. O fato de uma solução ser rápida de conferir não fornece, por si só, uma busca rápida.
Exercício: contar as arestas
No dodecaedro, cada um dos 20 vértices toca 3 arestas. Quantas arestas há? E quantas delas um ciclo hamiltoniano usa?
Contando por vértice, são $20 \times 3 = 60$ pontas de arestas, e cada aresta tem duas pontas: $60 / 2 = 30$ arestas. Um ciclo hamiltoniano passa por 20 vértices e volta, usando 20 arestas; as outras 10 ficam de fora.
Exercício: um ciclo no cubo
Os vértices do cubo podem ser escritos como as sequências de três bits, de $000$ a $111$, ligadas quando diferem em um só bit. Encontre um ciclo hamiltoniano.
Uma solução: $000 \to 001 \to 011 \to 010 \to 110 \to 111 \to 101 \to 100 \to 000$. Cada passo muda um único bit. Essa sequência é o código de Gray de três bits, usado em sensores de posição e em correção de erros justamente porque cada passo muda um só dígito.
Fontes: William Rowan Hamilton, “Memorandum respecting a new System of Roots of Unity”, Philosophical Magazine (1856) · Norman L. Biggs, E. Keith Lloyd e Robin J. Wilson, Graph Theory 1736–1936 (1976) · Richard M. Karp, “Reducibility among combinatorial problems” (1972) · o jogo icosiano na Matemateca IME-USP.
Todos os tópicos de William Rowan Hamilton · ← O teorema de Cayley–Hamilton · O legado de William Rowan Hamilton →