En teoría de grafos , un grafo de caballo , o grafo de recorrido de caballo , es un grafo que representa todos los movimientos legales de la pieza de ajedrez del caballo en un tablero de ajedrez . Cada vértice de este grafo representa una casilla del tablero de ajedrez, y cada arista conecta dos casillas que están a un movimiento de caballo una de la otra. Más específicamente, un grafo de caballo es un grafo de caballo de un tablero de ajedrez. [1] Sus vértices se pueden representar como los puntos del plano euclidiano cuyas coordenadas cartesianas son números enteros con y (los puntos en los centros de las casillas del tablero de ajedrez), y con dos vértices conectados por una arista cuando su distancia euclidiana es .
Para un gráfico de caballo, el número de vértices es . Si y entonces el número de aristas es (de lo contrario no hay aristas). Para un gráfico de caballo, 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 el grafo del caballo es un recorrido del caballo (cerrado) . [1] Un tablero de ajedrez con un número impar de casillas no tiene recorrido, porque el grafo del caballo es un grafo bipartito (cada color de casillas se puede usar como uno de dos conjuntos independientes , y los movimientos del caballo siempre cambian el color de las casillas) y solo los grafos bipartitos con un número par de vértices pueden tener ciclos hamiltonianos. La mayoría de los tableros de ajedrez con un número par de casillas tienen un recorrido del caballo; el teorema de Schwenk proporciona una lista exacta de cuáles lo tienen y cuáles no. [3]
Cuando se modifica para tener condiciones de contorno toroidales (lo que significa que un caballo no está bloqueado por el borde del tablero, sino que continúa hacia el borde opuesto), el gráfico del caballo es el mismo que el gráfico del hipercubo de cuatro dimensiones . [3]
