Grafo de Hanoi

O gráfico de Hanói $H_3^7$

Na teoria dos grafos e na matemática recreativa, os grafos de Hanói são grafos não direcionados cujos vértices representam os estados possíveis da Torre de Hanói e cujas arestas representam movimentos permitidos entre dois de estados.

Construção

O gráfico de Hanói $H_3^5$ (discos pretos) derivados dos valores ímpares no triângulo de Pascal

O quebra-cabeça consiste em um conjunto de discos de diferentes tamanhos, colocados em ordem crescente de tamanho sobre um conjunto fixo de torres. O gráfico de Hanói para um quebra-cabeça com $n$ discos ligados $k$ torres é denotada $H_k^n$ . Predefinição:Referências múltiplas Cada estado do quebra-cabeça é determinado pela escolha de uma torre para cada disco, então o gráfico tem $k^n$ vértices. Predefinição:Referências múltiplas

Nos movimentos do quebra-cabeça, o menor disco de uma torre é movido para uma torre desocupada ou para uma torre em que o menor disco é maior. Se houver $u$ torres desocupadas, o número de movimentos permitidos é

$(\genfrac{}{}{0ex}{}{k}{2})-(\genfrac{}{}{0ex}{}{u}{2}),$

que varia de no máximo $(\genfrac{}{}{0ex}{}{k}{2})$ (quando $u$ é zero ou um e $(\genfrac{}{}{0ex}{}{u}{2})$ é zero) até $k-1$ (quando todos os discos estão em uma torre e $u$ é $k-1$ ). Portanto, os graus dos vértices no gráfico de Hanói variam de um máximo de $(\genfrac{}{}{0ex}{}{k}{2})$ a um mínimo de $k-1$ . O número total de arestas é Predefinição:Referências múltiplas

$\frac{1}{2}(\genfrac{}{}{0ex}{}{k}{2})(k^n-(k-2{)}^n).$

Para $k=0$ (sem discos) existe apenas um estado do quebra-cabeça e um vértice do gráfico. Para $k>0$, o gráfico de Hanói $H_k^n$ pode ser decomposto em $k$ cópias do gráfico menor de Hanói $H_k^{n-1}$, um para cada posicionamento do maior disco. Essas cópias são conectadas entre si apenas nos estados em que o disco maior está livre para se mover, ou seja, é o único disco em sua torre e alguma outra torre está desocupada. Predefinição:Referências múltiplas

Propriedades gerais

$H_3^3$ com 12 arestas excluídas para produzir um caminho hamiltoniano

Todo gráfico de Hanói contém um caminho hamiltoniano . Predefinição:Referências múltiplas

O gráfico de Hanói $H_k^1$ é um grafo completo em $k$ vértices. Por conterem grafos completos, todos os grafos maiores de Hanói $H_k^n$ exigem pelo menos $k$ cores em qualquer coloração de grafos . Eles podem ser coloridos com exatamente $k$ cores usando a soma dos índices das torres contendo cada disco módulo $k$ como a cor. Predefinição:Referências múltiplas

Três torres

Um caso particular que foi bem estudado desde o trabalho de Predefinição:Harvtxt, dos grafos de Hanói é o caso $H_3^n$ com 3 torres.

Esses grafos possuem Predefinição:Math vértices (Predefinição:Oeis) e Predefinição:Math arestas (Predefinição:Oeis).

Eles são grafos de moedas (o grafo de contado de discos unitários que não se sobrepõem), com um arranjo de discos que lembra o triângulo de Sierpinski. Uma das maneiras de construir esse arranjo é a partir dos números do triângulo de Pascal postos em uma grade hexagonal com os números ímpares preenchidos com um disco unitário. O diametro desses grafos, e o comprimento da solução para a forma padrão da Torre de Hanoi (em que todos os discos começam em uma torre e devem terminar em outra) é $2^n-1$.Predefinição:R

Mais de três torres

Para $k>3$, a estrutura dos grafos de Hanói não é tão bem compreendida e o diâmetro desses grafos é desconhecido. Predefinição:Referências múltiplas Quando $k>4$ e $n>0$ ou quando $k=4$ e $n>2$, esses grafos não são planos. Predefinição:Referências múltiplas

Veja também

• Triângulo de Sierpinski