En la teoría de grafos , un gráfico de caballero , o un gráfico problema del caballo , es un gráfico que representa todos los movimientos legales del caballero de ajedrez piezas en un tablero de ajedrez . Cada vértice de este gráfico representa un cuadrado del tablero de ajedrez, y cada borde conecta dos cuadrados separados entre sí por el movimiento de un caballo. Más específicamente, un La gráfica de caballero es la gráfica de un caballero de un tablero de ajedrez. [1] Sus vértices se pueden representar como los puntos del plano euclidiano cuyas coordenadas cartesianas son enteros con y (los puntos en los centros de los cuadrados del tablero de ajedrez), y con dos vértices conectados por un borde cuando su distancia euclidiana es.
Gráfico de caballero | |
---|---|
Vértices | |
Bordes | (Si y ) |
Circunferencia | 4 (si y ) |
Propiedades | bipartito |
Tabla de gráficos y parámetros |
Por un gráfico de caballero, el número de vértices es . Si y entonces el número de aristas es (de lo contrario, no hay bordes). Por un gráfico de caballero, estos se simplifican de modo que el número de vértices es y el número de aristas es . [2]
Un ciclo hamiltoniano en la gráfica del caballero es un recorrido de caballero (cerrado) . [1] Un tablero de ajedrez con un número impar de cuadrados no tiene recorrido, porque el gráfico del caballo es un gráfico bipartito y solo los gráficos bipartitos con un número par de vértices pueden tener ciclos hamiltonianos. Todos, excepto un número limitado de tableros de ajedrez con un número par de casillas, tienen un recorrido de caballero; El teorema de Schwenk proporciona una lista exacta de cuáles lo hacen y cuáles no. [3]
Cuando se modifica para tener condiciones de límite toroidales (lo que significa que un caballo no está bloqueado por el borde del tablero, sino que continúa hacia el borde opuesto) elEl gráfico de caballero es el mismo que el gráfico del hipercubo de cuatro dimensiones . [3]
Ver también
Referencias
- ^ a b Averbach, Bonnie; Chein, Orin (1980), Resolución de problemas mediante matemáticas recreativas , Dover, pág. 195, ISBN 9780486131740.
- ^ Sloane, N. J. A. (ed.). "Secuencia A033996" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ a b Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems. Paradojas, perplejidades y acertijos matemáticos para el que se rasca la cabeza en serio , Princeton University Press, págs. 44, 68, ISBN 978-0-691-15498-5.