En teoría de grafos y matemáticas recreativas , los gráficos de Hanoi son gráficos no dirigidos cuyos vértices representan los posibles estados del rompecabezas de la Torre de Hanoi , y cuyos bordes representan movimientos permitidos entre pares de estados.
Construcción
El rompecabezas consiste en un conjunto de discos de diferentes tamaños, colocados en orden creciente de tamaño en un conjunto fijo de torres. El gráfico de Hanoi para un rompecabezas con discos en torres se denota . [1] [2] Cada estado del rompecabezas está determinado por la elección de una torre para cada disco, por lo que el gráfico tienevértices. [2]
En los movimientos del rompecabezas, el disco más pequeño de una torre se mueve a una torre desocupada oa una torre cuyo disco más pequeño es más grande. Si hay torres desocupadas, el número de movimientos permitidos es
que va desde un máximo de (Cuándo es cero o uno y es cero) a (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 a un mínimo de . El número total de aristas es [3]
Para (sin discos) solo hay un estado del rompecabezas y un vértice del gráfico. Para, el gráfico de Hanoi se puede descomponer en copias del gráfico más pequeño de Hanoi , uno para cada ubicación del disco más grande. Estas copias están conectadas entre sí solo en los estados donde el disco más grande se puede mover libremente: es el único disco en su torre y alguna otra torre está desocupada. [4]
Propiedades generales
Cada gráfico de Hanoi contiene un ciclo hamiltoniano . [5]
El gráfico de Hanoi es un gráfico completo envértices. Debido a que contienen gráficos completos, todos los gráficos más grandes de Hanoi requiere al menos colores en cualquier color de gráfico . Pueden estar coloreados exactamente colores sumando los índices de las torres que contienen cada disco, y usando el módulo de suma como el color. [3]
Tres torres
Un caso particular de los gráficos de Hanoi que ha sido bien estudiado desde el trabajo de Scorer, Grundy & Smith (1944) [1] [6] es el caso de los gráficos de Hanoi de tres torres,. Estos gráficos tienen 3 n vértices ( OEIS : A000244 ) y3 (3 n - 1)/2 bordes ( OEIS : A029858 ). [7] Son gráficos de centavo (los gráficos de contacto de discos unitarios que no se superponen 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 disponer los números del triángulo de Pascal en los puntos de una celosía hexagonal , con un espaciado unitario, y colocar un disco unitario en cada punto cuyo número sea impar. El diámetro de estos gráficos 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 deben moverse a otra torre) es. [2]
Más de tres torres
¿Cuál es el diámetro de las gráficas? por ?
Para , la estructura de los gráficos de Hanoi no se comprende tan bien y se desconoce el diámetro de estos gráficos. [2] Cuando y o cuando y , estos gráficos no son planos. [5]
Referencias
- ↑ a b 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. 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 Gráficos de Hanoi", Temas de teoría de gráficos: gráficos y su producto cartesiano , Wellesley, MA: AK Peters, págs. 13-15, ISBN 978-1-56881-429-2, MR 2468851
- ^ a b Arett, Danielle; Dorée, Suzanne (2010), "Colorear y contar en los gráficos de la Torre de Hanoi", Revista de matemáticas , 83 (3): 200–209, doi : 10.4169 / 002557010X494841 , MR 2668333
- ^ Stewart, Ian (2003), "Capítulo 1: El león, la llama y la lechuga", Otra buena matemática en la que me has metido , Mineola, NY: Dover Publications, ISBN 0-486-43181-9, MR 2046372
- ^ a b 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 , MR 1924112
- ^ Anotador, RS; Grundy, PM ; Smith, CAB (julio de 1944), "Algunos juegos binarios", The Mathematical Gazette , 28 (280): 96, doi : 10.2307 / 3606393
- ^ http://mathworld.wolfram.com/HanoiGraph.html