Gráfico de Hanoi

Patrón de estados y movimientos en el rompecabezas de la Torre de Hanoi

El gráfico de Hanoi ${\displaystyle H_{3}^{7}}$

En teoría de grafos y matemáticas recreativas , los grafos de Hanoi son grafos no dirigidos cuyos vértices representan los estados posibles del rompecabezas de la Torre de Hanoi y cuyos bordes representan movimientos permitidos entre pares de estados.

Construcción

El gráfico de Hanoi (discos negros) derivado de los valores impares en el triángulo de Pascal ${\displaystyle H_{3}^{5}}$

El rompecabezas consiste en un conjunto de discos de diferentes tamaños, colocados en orden creciente de tamaño sobre un conjunto fijo de torres. El gráfico de Hanoi para un rompecabezas con discos sobre torres se denota como . ^{[1] [2]} Cada estado del rompecabezas está determinado por la elección de una torre para cada disco, por lo que el gráfico tiene vértices. ^[2] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle H_{k}^{n}}$ ${\displaystyle k^{n}}$

En los movimientos del rompecabezas, el disco más pequeño de una torre se mueve a una torre desocupada o a una torre cuyo disco más pequeño es más grande. Si hay torres desocupadas, el número de movimientos permitidos es ${\displaystyle u}$

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

que va desde un máximo de (cuando es cero o uno y es cero) hasta (cuando todos los discos están en una torre y es ). Por lo tanto, los grados de los vértices en el gráfico de Hanoi van desde un máximo de hasta un mínimo de . El número total de aristas es ^[3] ${\displaystyle {\tbinom {k}{2}}}$ ${\displaystyle u}$ ${\displaystyle {\tbinom {u}{2}}}$ ${\displaystyle k-1}$ ${\displaystyle u}$ ${\displaystyle k-1}$ ${\displaystyle {\tbinom {k}{2}}}$ ${\displaystyle k-1}$

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

Para (sin discos) solo hay un estado del rompecabezas y un vértice del grafo. Para , el grafo de Hanoi se puede descomponer en copias del grafo de Hanoi más pequeño , una para cada ubicación del disco más grande. Estas copias están conectadas entre sí solo en estados donde el disco más grande es libre de moverse: es el único disco en su torre y alguna otra torre está desocupada. ^[4] ${\displaystyle k=0}$ ${\displaystyle k>0}$ ${\displaystyle H_{k}^{n}}$ ${\displaystyle k}$ ${\displaystyle H_{k}^{n-1}}$

Propiedades generales

${\displaystyle H_{3}^{3}}$con 12 aristas eliminadas para producir un ciclo hamiltoniano

Cada gráfico de Hanoi contiene un ciclo hamiltoniano . ^[5]

El grafo de Hanoi es un grafo completo sobre vértices. Debido a que contienen grafos completos, todos los grafos de Hanoi más grandes requieren al menos colores en cualquier coloración de grafos . Se pueden colorear con exactamente los colores sumando los índices de las torres que contienen cada disco y usando el módulo de la suma como el color. ^[3] ${\displaystyle H_{k}^{1}}$ ${\displaystyle k}$ ${\displaystyle H_{k}^{n}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Tres torres

Un caso particular de los grafos de Hanoi que ha sido bien estudiado desde el trabajo de Scorer, Grundy y Smith (1944) ^{[1] [6]} es el caso de los grafos de Hanoi de tres torres, . Estos grafos tienen 3 n vértices ( OEIS : A000244 ) y ⁠ ${\displaystyle H_{3}^{n}}$ 3( ³ⁿ -1)/2⁠ aristas ( OEIS : A029858 ). ^[7] Son grafos de centavo (los grafos de contacto de discos unitarios no superpuestos en el plano), con una disposición de discos que se asemeja al triángulo de Sierpinski . Una forma de construir esta disposición es organizar los números del triángulo de Pascal en los puntos de una red hexagonal , con espaciado unitario, y colocar un disco unitario en cada punto cuyo número sea impar. El diámetro de estos grafos y la longitud de la solución a la forma estándar del rompecabezas de la Torre de Hanoi (en el que todos los discos comienzan en una torre y todos deben moverse a otra torre) es. ^[2] ${\displaystyle 2^{n}-1}$

Más de tres torres

Problema sin resolver en matemáticas :

¿Cuál es el diámetro de los gráficos ? ${\displaystyle H_{k}^{n}}$ ${\displaystyle k>3}$

(más problemas sin resolver en matemáticas)

Para , la estructura de los grafos de Hanoi no se entiende tan bien, y se desconoce el diámetro de estos grafos. ^[2] Cuando y o cuando y , estos grafos no son planos. ^[5] ${\displaystyle k>3}$ ${\displaystyle k>4}$ ${\displaystyle n>0}$ ${\displaystyle k=4}$ ${\displaystyle n>2}$

Véase también

• Triángulo de Sierpinski

Referencias

1. Hinz, Andreas M.; Klavžar, Sandi ; Petr, Ciril (2018), "2.3 Gráficos de Hanoi", La torre de Hanoi: mitos y matemáticas (2.ª ed.), Cham: Birkhäuser, pág. 120, doi :10.1007/978-3-319-73779-9, ISBN 978-3-319-73778-2, Sr.  3791459
2. Imrich, Wilfried ; Klavžar, Sandi ; Rall, Douglas F. (2008), "2.2 Gráficos de Hanoi", Temas de teoría de grafos: gráficos y su producto cartesiano , Wellesley, MA: AK Peters, págs. 13-15, ISBN 978-1-56881-429-2, Sr.  2468851
3. Arett, Danielle; Dorée, Suzanne (2010), "Colorear y contar en los gráficos de la Torre de Hanoi", Mathematics Magazine , 83 (3): 200–209, doi :10.4169/002557010X494841, MR  2668333, S2CID  120868360
4. Stewart, Ian (2003), "Capítulo 1: El león, la llama y la lechuga", Another Fine Math You've Got Me Into , Mineola, NY: Dover Publications, ISBN 0-486-43181-9, Sr.  2046372
5. Hinz, Andreas M.; Parisse, Daniele (2002), "Sobre la planaridad de los gráficos de Hanoi", Expositiones Mathematicae , 20 (3): 263–268, doi : 10.1016/S0723-0869(02)80023-8 , SEÑOR  1924112
6. Scorer, RS; Grundy, PM ; Smith, CAB (julio de 1944), "Algunos juegos binarios", The Mathematical Gazette , 28 (280): 96, doi :10.2307/3606393, JSTOR  3606393, S2CID  125099183
7. "Gráfico de Hanoi".