Mostrar código-fonte de Grafo de Hanoi


[[Ficheiro:Hanoi-Graph-7.svg|miniaturadaimagem| O gráfico de Hanói <math>H^7_3</math>]]
Na [[teoria dos grafos]] e [[Matemática recreativa|na matemática recreativa]], os '''grafos de Hanói''' são [[Grafo|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 ==
[[Ficheiro:Sierpinski_Pascal_triangle.svg|miniaturadaimagem| O gráfico de Hanói <math>H^5_3</math> (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 <math>n</math> discos ligados <math>k</math> torres é denotada <math>H^n_k</math> . {{Referências múltiplas|hkp|ikr}}  Cada estado do quebra-cabeça é determinado pela escolha de uma torre para cada disco, então o gráfico tem <math>k^n</math> vértices. {{Referências múltiplas|ikr}}

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 <math>u</math> torres desocupadas, o número de movimentos permitidos é

: <math>\binom{k}{2}-\binom{u}{2},</math>

que varia de no máximo <math>\tbinom{k}{2}</math> (quando <math>u</math> é zero ou um e <math>\tbinom{u}{2}</math> é zero) até <math>k-1</math> (quando todos os discos estão em uma torre e <math>u</math> é <math>k-1</math> ). Portanto, os [[Grau (teoria dos grafos)|graus]] dos vértices no gráfico de Hanói variam de um máximo de <math>\tbinom{k}{2}</math> a um mínimo de <math>k-1</math> . O número total de arestas é {{Referências múltiplas|ad}}

: <math>\frac{1}{2}\binom{k}{2}\bigl(k^n-(k-2)^n\bigr).</math>

Para <math>k=0</math> (sem discos) existe apenas um estado do quebra-cabeça e um vértice do gráfico. Para <math>k > 0</math>, o gráfico de Hanói <math>H^n_k</math> pode ser decomposto em <math>k</math> cópias do gráfico menor de Hanói <math>H^{n-1}_k</math>, 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. {{Referências múltiplas|afm}}

== Propriedades gerais ==
[[Ficheiro:Tower_of_hanoi_graph.svg|lang=cy|miniaturadaimagem|300x300px| <math>H^3_3</math> com 12 arestas excluídas para produzir um caminho hamiltoniano]]
Todo gráfico de Hanói contém um [[caminho hamiltoniano]] . {{Referências múltiplas|hp}}

O gráfico de Hanói <math>H^1_k</math> é um [[grafo completo]] em <math>k</math> vértices. Por conterem grafos completos, todos os grafos maiores de Hanói <math>H^n_k</math> exigem pelo menos <math>k</math> cores em qualquer [[coloração de grafos]] . Eles podem ser coloridos com exatamente <math>k</math> cores usando a soma dos índices das torres contendo cada disco módulo <math>k</math> como a cor. {{Referências múltiplas|ad}}

== Três torres ==
Um caso particular que foi bem estudado desde o trabalho de {{harvtxt|Scorer|Grundy|Smith|1944}}, dos grafos de Hanói é o caso <math>H^n_3</math> com 3 torres.

Esses grafos possuem {{math|[[Power of three|3<sup>''n''</sup>]]}} [[:en:Vertex_(graph_theory)|vértices]] ({{oeis|A000244}}) e {{math|{{sfrac|3(3<sup>''n''</sup> &minus; 1)|2}}}}  [[:en:Glossary_of_graph_theory#edge|arestas]] ({{oeis|A029858}}).<ref>{{Cite web|url=http://mathworld.wolfram.com/HanoiGraph.html|title=Hanoi Graph}}</ref>

Eles são [[:en:Penny_graph|grafos de moedas]] (o [[:en:Contact_graph|grafo de contado]] de discos unitários que não se sobrepõem), com um arranjo de discos que lembra o [[:en:Sierpinski_triangle|triângulo de Sierpinski]]. Uma das maneiras de construir esse arranjo é a partir dos números do [[:en:Pascal's_triangle|triângulo de Pascal]] postos em uma grade hexagonal com os números ímpares preenchidos com um disco unitário. O [[:en:Distance_(graph_theory)|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) é <math>2^{n}-1</math>.{{r|ikr}}

== Mais de três torres ==
<div style="clear:right;"></div>{{Não resolvido|mathematics|Qual é o diâmetro dos grafos <math>H^n_k</math> para <math>k > 3</math>?}}
Para <math>k > 3</math>, a estrutura dos grafos de Hanói não é tão bem compreendida e o diâmetro desses grafos é desconhecido. {{Referências múltiplas|ikr}} Quando <math>k > 4</math> e <math>n > 0</math> ou quando <math>k = 4</math> e <math>n > 2</math>, esses grafos não são planos. {{Referências múltiplas|hp}}

== Veja também ==

* [[Triângulo de Sierpinski]]

== Referências ==
{{Reflist|refs=<ref name=ad>{{citation
 | last1 = Arett | first1 = Danielle
 | last2 = Dorée | first2 = Suzanne | author2-link = Suzanne Dorée
 | doi = 10.4169/002557010X494841
 | issue = 3
 | journal = Mathematics Magazine
 | mr = 2668333
 | pages = 200–209
 | title = Coloring and counting on the Tower of Hanoi graphs
 | volume = 83
 | year = 2010| s2cid = 120868360
 }}</ref>

<ref name=afm>{{citation
 | last = Stewart | first = Ian | author-link = Ian Stewart (mathematician)
 | isbn = 0-486-43181-9
 | mr = 2046372
 | contribution = Chapter 1: The Lion, the Llama, and the Lettuce
 | publisher = Dover Publications | location = Mineola, NY
 | title = Another Fine Math You've Got Me Into
 | year = 2003}}</ref>
 
<ref name=hkp>{{citation
 | last1 = Hinz | first1 = Andreas M.
 | last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar
 | last3 = Petr | first3 = Ciril
 | contribution = 2.3 Hanoi Graphs
 | doi = 10.1007/978-3-319-73779-9
 | edition = 2nd
 | isbn = 978-3-319-73778-2
 | location = Cham
 | mr = 3791459
 | page = 120
 | publisher = Birkhäuser
 | title = The tower of Hanoi—myths and maths
 | title-link = The Tower of Hanoi – Myths and Maths
 | year = 2018}}</ref>

<ref name=hp>{{citation
 | last1 = Hinz | first1 = Andreas M.
 | last2 = Parisse | first2 = Daniele
 | doi = 10.1016/S0723-0869(02)80023-8
 | issue = 3
 | journal = Expositiones Mathematicae
 | mr = 1924112
 | pages = 263–268
 | title = On the planarity of Hanoi graphs
 | volume = 20
 | year = 2002| doi-access = free
 }}</ref>

<ref name=ikr>{{citation
 | last1 = Imrich | first1 = Wilfried | author1-link = Wilfried Imrich
 | last2 = Klavžar | first2 = Sandi | author2-link = Sandi Klavžar
 | last3 = Rall | first3 = Douglas F.
 | contribution = 2.2 Hanoi Graphs
 | isbn = 978-1-56881-429-2
 | location = Wellesley, MA
 | mr = 2468851
 | pages = 13–15
 | publisher = A K Peters
 | title = Topics in Graph Theory: Graphs and their Cartesian Product
 | year = 2008}}</ref>

<ref name=sgs>{{citation
 | last1 = Scorer | first1 = R. S.
 | last2 = Grundy | first2 = P. M. | author2-link = Patrick Michael Grundy
 | last3 = Smith | first3 = C. A. B. | author3-link = Cedric Smith (statistician)
 | date = July 1944
 | doi = 10.2307/3606393
 | issue = 280
 | journal = The Mathematical Gazette
 | page = 96
 | title = Some binary games
 | volume = 28| jstor = 3606393
 | s2cid = 125099183
 }}</ref>}}