Gráfica del rey

En la teoría del gráfico, un Gráfico del rey es un gráfico que representa todos los movimientos legales de la pieza de ajedrez rey en un tablero de ajedrez donde cada vértice representa un cuadrado en un tablero de ajedrez y cada borde es un movimiento legal. Más específicamente, un ${\displaystyle n\times m}$ El gráfico del rey es un gráfico del rey de un ${\displaystyle n\times m}$ ajedrez. Es el gráfico de mapa formado de los cuadrados de un tablero de ajedrez haciendo un vértice para cada cuadrado y un borde para cada dos cuadrados que comparten un borde o una esquina. También se puede construir como el producto fuerte de dos gráficos de ruta.

Para un ${\displaystyle n\times m}$ el gráfico del rey el número total de vértices es ${\displaystyle nm}$ y el número de bordes es ${\displaystyle 4nm-3(n+m)+2}$. Para un cuadrado ${\displaystyle n\times n}$ el gráfico del rey esto simplifica para que el número total de vértices es ${\displaystyle n^{2}$ y el número total de bordes es ${\displaystyle (2n-2)(2n-1)}$.

El entorno de un vértice en el grafo de rey corresponde al entorno de Moore para autómatas celulares. Una generalización del grafo de rey, llamada grafo de rey, se forma a partir de un grafo cuadrado (un grafo plano en el que cada cara acotada es un cuadrilátero y cada vértice interior tiene al menos cuatro vecinos) sumando las dos diagonales de cada cara cuadrilátera del grafo cuadrado.

En el dibujo del gráfico del rey obtenido de un ${\displaystyle n\times m}$ ajedrez, hay ${\displaystyle (n-1)(m-1)}$ cruces, pero es posible obtener un dibujo con menos cruces conectando a los dos vecinos más cercanos de cada esquina cuadrado por una curva fuera del tablero de ajedrez en lugar de por un segmento de línea diagonal. De esta manera, ${\displaystyle (n-1)(m-1)-4}$ Los cruces siempre son posibles. Para el gráfico del rey de los pequeños tableros de ajedrez, otros dibujos conducen a incluso menos cruces; en particular cada ${\displaystyle 2\times n}$ El gráfico del rey es un gráfico plano. Sin embargo, cuando ambos ${\displaystyle n}$ y ${\displaystyle m}$ son al menos cuatro, y no son ambos iguales a cuatro, ${\displaystyle (n-1)(m-1)-4}$ es el número óptimo de cruces.

• Gráfico del caballero
• Gráfico de la reina
• Gráfico de Rook
• Gráfico de Bishop
• Gráfico de celos
• Portal de Ajedrez