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}$ . 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.

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 é

${\binom {k}{2}}-{\binom {u}{2}},$

que varia de no máximo ${\tbinom {k}{2}}$ (quando $u$ é zero ou um e ${\tbinom {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 ${\tbinom {k}{2}}$ a um mínimo de $k-1$ . O número total de arestas é

${\frac {1}{2}}{\binom {k}{2}}{\bigl (}k^{n}-(k-2)^{n}{\bigr )}.$

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.

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 .

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.

Três torres

Um caso particular que foi bem estudado desde o trabalho de Scorer, Grundy & Smith (1944), dos grafos de Hanói é o caso $H_{3}^{n}$ com 3 torres.

Esses grafos possuem 3ⁿ vértices (Predefinição:Oeis) e 3(3ⁿ − 1)2 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$.

Olá, Grafo de Hanoi. Você tem novas mensagens na página de discussão de Ikr.
Pode retirar esse aviso a qualquer momento removendo a predefinição {{resposta}} ou {{R}} .

Mais de três torres

Problema de mathematics em aberto:

Qual é o diâmetro dos grafos $H_{k}^{n}$ para $k>3$?

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

Veja também

• Triângulo de Sierpinski