Hanoi graph: Difference between revisions
→General properties: Add H^3_3 graph of Hamiltonian cycle |
Citation bot (talk | contribs) Add: s2cid. | Use this bot. Report bugs. | Suggested by Abductive | Category:Planar graphs | #UCB_Category 11/89 |
||
(8 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{Short description|Pattern of states and moves in the Tower of Hanoi puzzle}} |
||
[[File:Hanoi-Graph-7.svg|thumb|The Hanoi graph <math>H^7_3</math>]] |
[[File:Hanoi-Graph-7.svg|thumb|The Hanoi graph <math>H^7_3</math>]] |
||
In [[graph theory]] and [[recreational mathematics]], the '''Hanoi graphs''' are [[undirected graph]]s whose vertices represent the possible states of the [[Tower of Hanoi]] puzzle, and whose edges represent allowable moves between pairs of states. |
In [[graph theory]] and [[recreational mathematics]], the '''Hanoi graphs''' are [[undirected graph]]s whose vertices represent the possible states of the [[Tower of Hanoi]] puzzle, and whose edges represent allowable moves between pairs of states. |
||
Line 26: | Line 26: | ||
==Three towers== |
==Three towers== |
||
A particular case of the Hanoi graphs that has been well studied since the work of {{harvtxt|Scorer|Grundy|Smith|1944}}{{r|hkp|sgs}} is the case of the three-tower Hanoi graphs, <math>H^n_3</math>. These graphs have {{math|[[Power of three|3<sup>''n''</sup>]]}} [[vertex (graph theory)|vertices]]. |
A particular case of the Hanoi graphs that has been well studied since the work of {{harvtxt|Scorer|Grundy|Smith|1944}}{{r|hkp|sgs}} is the case of the three-tower Hanoi graphs, <math>H^n_3</math>. These graphs have {{math|[[Power of three|3<sup>''n''</sup>]]}} [[vertex (graph theory)|vertices]] ({{oeis|A000244}}) and {{math|{{sfrac|3(3<sup>''n''</sup> − 1)|2}} }} [[glossary_of_graph_theory#edge|edges]] ({{oeis|A029858}}).<ref>{{Cite web|url=http://mathworld.wolfram.com/HanoiGraph.html|title = Hanoi Graph}}</ref> |
||
They are [[penny graph]]s (the [[contact graph]]s of non-overlapping unit disks in the plane), with an arrangement of disks that resembles the [[Sierpinski triangle]]. One way of constructing this arrangement is to arrange the numbers of [[Pascal's triangle]] on the points of a [[hexagonal lattice]], with unit spacing, and place a unit disk on each point whose number is odd. |
They are [[penny graph]]s (the [[contact graph]]s of non-overlapping unit disks in the plane), with an arrangement of disks that resembles the [[Sierpinski triangle]]. One way of constructing this arrangement is to arrange the numbers of [[Pascal's triangle]] on the points of a [[hexagonal lattice]], with unit spacing, and place a unit disk on each point whose number is odd. |
||
The [[Distance (graph theory)|diameter]] of these graphs, and the length of the solution to the standard form of the Tower of Hanoi puzzle (in which the disks all start on one tower and must all move to one other tower) is <math>2^{n}-1</math>.{{r|ikr}} |
The [[Distance (graph theory)|diameter]] of these graphs, and the length of the solution to the standard form of the Tower of Hanoi puzzle (in which the disks all start on one tower and must all move to one other tower) is <math>2^{n}-1</math>.{{r|ikr}} |
||
==More than three towers== |
==More than three towers== |
||
{{unsolved|mathematics|What is the diameter of the graphs <math>H^n_k</math> for <math>k > 3</math>?}} |
<div style="clear:right;"></div>{{unsolved|mathematics|What is the diameter of the graphs <math>H^n_k</math> for <math>k > 3</math>?}} |
||
For <math>k > 3</math>, the structure of the Hanoi graphs is not as well understood, and the diameter of these graphs is unknown.{{r|ikr}} |
For <math>k > 3</math>, the structure of the Hanoi graphs is not as well understood, and the diameter of these graphs is unknown.{{r|ikr}} |
||
When <math>k > 4</math> and <math>n > 0</math> or when <math>k = 4</math> and <math>n > 2</math>, these graphs are nonplanar.{{r|hp}} |
When <math>k > 4</math> and <math>n > 0</math> or when <math>k = 4</math> and <math>n > 2</math>, these graphs are nonplanar.{{r|hp}} |
||
== See also == |
|||
* [[Sierpinski triangle]] |
|||
==References== |
==References== |
||
Line 48: | Line 51: | ||
| title = Coloring and counting on the Tower of Hanoi graphs |
| title = Coloring and counting on the Tower of Hanoi graphs |
||
| volume = 83 |
| volume = 83 |
||
| year = 2010 |
| year = 2010| s2cid = 120868360 |
||
}}</ref> |
|||
<ref name=afm>{{citation |
<ref name=afm>{{citation |
||
Line 85: | Line 89: | ||
| title = On the planarity of Hanoi graphs |
| title = On the planarity of Hanoi graphs |
||
| volume = 20 |
| volume = 20 |
||
| year = 2002 |
| year = 2002| doi-access = free |
||
}}</ref> |
|||
<ref name=ikr>{{citation |
<ref name=ikr>{{citation |
||
Line 110: | Line 115: | ||
| page = 96 |
| page = 96 |
||
| title = Some binary games |
| title = Some binary games |
||
| volume = 28 |
| volume = 28| jstor = 3606393 |
||
| s2cid = 125099183 |
|||
}}</ref> |
|||
}} |
}} |
Latest revision as of 06:49, 2 June 2023
In graph theory and recreational mathematics, the Hanoi graphs are undirected graphs whose vertices represent the possible states of the Tower of Hanoi puzzle, and whose edges represent allowable moves between pairs of states.
Construction
[edit]The puzzle consists of a set of disks of different sizes, placed in increasing order of size on a fixed set of towers. The Hanoi graph for a puzzle with disks on towers is denoted .[1][2] Each state of the puzzle is determined by the choice of one tower for each disk, so the graph has vertices.[2]
In the moves of the puzzle, the smallest disk on one tower is moved either to an unoccupied tower or to a tower whose smallest disk is larger. If there are unoccupied towers, the number of allowable moves is
which ranges from a maximum of (when is zero or one and is zero) to (when all disks are on one tower and is ). Therefore, the degrees of the vertices in the Hanoi graph range from a maximum of to a minimum of . The total number of edges is[3]
For (no disks) there is only one state of the puzzle and one vertex of the graph. For , the Hanoi graph can be decomposed into copies of the smaller Hanoi graph , one for each placement of the largest disk. These copies are connected to each other only at states where the largest disk is free to move: it is the only disk in its tower, and some other tower is unoccupied.[4]
General properties
[edit]Every Hanoi graph contains a Hamiltonian cycle.[5]
The Hanoi graph is a complete graph on vertices. Because they contain complete graphs, all larger Hanoi graphs require at least colors in any graph coloring. They may be colored with exactly colors by summing the indexes of the towers containing each disk, and using the sum modulo as the color.[3]
Three towers
[edit]A particular case of the Hanoi graphs that has been well studied since the work of Scorer, Grundy & Smith (1944)[1][6] is the case of the three-tower Hanoi graphs, . These graphs have 3n vertices (OEIS: A000244) and 3(3n − 1)/2 edges (OEIS: A029858).[7] They are penny graphs (the contact graphs of non-overlapping unit disks in the plane), with an arrangement of disks that resembles the Sierpinski triangle. One way of constructing this arrangement is to arrange the numbers of Pascal's triangle on the points of a hexagonal lattice, with unit spacing, and place a unit disk on each point whose number is odd. The diameter of these graphs, and the length of the solution to the standard form of the Tower of Hanoi puzzle (in which the disks all start on one tower and must all move to one other tower) is .[2]
More than three towers
[edit]For , the structure of the Hanoi graphs is not as well understood, and the diameter of these graphs is unknown.[2] When and or when and , these graphs are nonplanar.[5]
See also
[edit]References
[edit]- ^ a b Hinz, Andreas M.; Klavžar, Sandi; Petr, Ciril (2018), "2.3 Hanoi Graphs", The tower of Hanoi—myths and maths (2nd ed.), Cham: Birkhäuser, p. 120, doi:10.1007/978-3-319-73779-9, ISBN 978-3-319-73778-2, MR 3791459
- ^ a b c d Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), "2.2 Hanoi Graphs", Topics in Graph Theory: Graphs and their Cartesian Product, Wellesley, MA: A K Peters, pp. 13–15, ISBN 978-1-56881-429-2, MR 2468851
- ^ a b Arett, Danielle; Dorée, Suzanne (2010), "Coloring and counting on the Tower of Hanoi graphs", Mathematics Magazine, 83 (3): 200–209, doi:10.4169/002557010X494841, MR 2668333, S2CID 120868360
- ^ Stewart, Ian (2003), "Chapter 1: The Lion, the Llama, and the Lettuce", Another Fine Math You've Got Me Into, Mineola, NY: Dover Publications, ISBN 0-486-43181-9, MR 2046372
- ^ a b Hinz, Andreas M.; Parisse, Daniele (2002), "On the planarity of Hanoi graphs", Expositiones Mathematicae, 20 (3): 263–268, doi:10.1016/S0723-0869(02)80023-8, MR 1924112
- ^ Scorer, R. S.; Grundy, P. M.; Smith, C. A. B. (July 1944), "Some binary games", The Mathematical Gazette, 28 (280): 96, doi:10.2307/3606393, JSTOR 3606393, S2CID 125099183
- ^ "Hanoi Graph".