Sobre a generalização do grafo da Torre de Hanoi

• Lia Martins UFAM / IFAM
• Jonas Costa UFAM
• Rosiane de Freitas UFAM

DOI: https://doi.org/10.5753/etc.2024.3006

Resumo

O jogo clássico da Torre de Hanoi (ToH) consiste em uma base com três pinos P = p₀, p₁, p₂ e um conjunto de n discos D = {d₁, d₂, ..., d_n} de diferentes tamanhos, sendo d_i < d_j se i < j. No estado inicial todos os discos estão empilhados em p₀ em ordem decrescente de tamanho, um estado regular perfeito. O objetivo do jogo é transferir todos os discos para p₂, nessa mesma disposição, obedecendo-se as seguintes regras: (1) pode-se mover apenas um disco de cada vez, e sempre o disco do topo de um dos pinos; (2) o disco d_i só pode ser colocado sobre d_j se i < j. Denota-se Hn o grafo da ToH com n discos. Hn caracteriza todos os estados regulares possíveis e os movimentos que podem ser feitos de um estado para outro. Neste trabalho é apresentado um algoritmo recursivo que, partindo do case base H₁ e de um ciclo C₆, gera o grafo da ToH para qualquer número de discos (H_n).

Referências

Poole, D. G. (1994). The towers and triangles of professor claus (or, pascal knows hanoi). Mathematics Magazine, 67(5):323–344.

Zhang, Z., Wu, S., Li, M., and Comellas, F. (2016). The number and degree distribution of spanning trees in the tower of hanoi graph. Theoretical Computer Science, 609:443–455.