En matemáticas, un grafo de reina es un grafo no dirigido que representa todos los movimientos legales de la reina —una pieza de ajedrez— en un tablero de ajedrez . En el grafo, cada vértice representa una casilla en un tablero de ajedrez, y cada arista es un movimiento legal que la reina puede hacer, es decir, un movimiento horizontal, vertical o diagonal de cualquier número de casillas. Si el tablero de ajedrez tiene dimensiones , entonces el grafo inducido se llama grafo de reina.
Los conjuntos independientes de los gráficos corresponden a las ubicaciones de varias reinas en las que no hay dos reinas atacándose entre sí. Se estudian en el rompecabezas de las ocho reinas , en el que se colocan ocho reinas que no atacan en un tablero de ajedrez estándar. Los conjuntos dominantes representan disposiciones de reinas en las que cada casilla está atacada u ocupada por una reina; cinco reinas, pero no menos, pueden dominar el tablero de ajedrez.
Los colores de los gráficos representan formas de colorear cada cuadrado de modo que una reina no pueda moverse entre dos cuadrados del mismo color; se necesitan al menos n colores para un tablero de ajedrez, pero se necesitan 9 colores para el tablero.
Existe un ciclo hamiltoniano para cada grafo de reina, y los grafos son biconexos (permanecen conectados si se elimina cualquier vértice). Los casos especiales de los grafos de reina y son completos . [1]
Un conjunto independiente del grafo corresponde a una colocación de varias reinas en un tablero de ajedrez de tal manera que no haya dos reinas atacándose entre sí. En un tablero de ajedrez, el conjunto independiente más grande contiene como máximo n vértices, ya que no puede haber dos reinas en la misma fila o columna. [2] Este límite superior se puede lograr para todos los n excepto n = 2 y n = 3. [3] En el caso de n = 8, este es el tradicional rompecabezas de las ocho reinas. [2]
Un conjunto dominante del grafo de la reina corresponde a una colocación de las reinas de tal manera que cada casilla del tablero de ajedrez está atacada u ocupada por una reina. En un tablero de ajedrez, cinco reinas pueden dominar, y este es el número mínimo posible [4] : 113-114 (cuatro reinas dejan al menos dos casillas sin atacar). Hay 4.860 colocaciones de este tipo de cinco reinas, incluidas aquellas en las que las reinas controlan también todas las casillas ocupadas, es decir, se atacan y se protegen mutuamente. En este subgrupo, también hay posiciones en las que las reinas ocupan casillas en la diagonal principal solamente [4] : 113-114 (por ejemplo, de a1 a h8), o todas en una subdiagonal (por ejemplo, de a2 a g8). [5] [6]
Modificar el gráfico reemplazando el tablero de ajedrez rectangular sin bucles por un toro o un cilindro reduce el tamaño mínimo del conjunto dominante a cuatro. [4] : 139
El grafo de la reina está dominado por el único vértice en el centro del tablero. El vértice central del grafo de la reina es adyacente a todos los vértices excepto a 8: aquellos vértices que son adyacentes al vértice central del grafo del caballo . [4] : 117
Defina el número de dominación d ( n ) de un grafo de reina como el tamaño del conjunto dominante más pequeño, y el número de dominación diagonal dd ( n ) como el tamaño del conjunto dominante más pequeño que es un subconjunto de la diagonal larga. Nótese que para todo n . El límite se alcanza para , pero no para . [4] : 119
El número de dominación es lineal en n , con límites dados por: [4] : 119, 121
Los valores iniciales de d ( n ), para , son 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5 (secuencia A075458 en la OEIS ).
Sea K n el tamaño máximo de un subconjunto de tal que cada número tiene la misma paridad y no hay tres números que formen una progresión aritmética (el conjunto está "libre de puntos medios"). El número de dominación diagonal de un grafo de reina es . [4] : 116
Defina el número de dominación independiente ID ( n ) como el tamaño del conjunto dominante independiente más pequeño en un grafo de reina. Se sabe que . [7]
La coloración del grafo de la reina consiste en asignar colores a cada vértice de forma que no haya dos vértices adyacentes con el mismo color. Por ejemplo, si a8 está coloreado de rojo, ninguna otra casilla de la columna a , la octava fila o la diagonal larga puede colorearse de rojo, ya que una reina puede moverse desde a8 a cualquiera de estas casillas. El número cromático del grafo es el número más pequeño de colores que se pueden utilizar para colorearlo.
En el caso de un grafo de reina, se requieren al menos n colores, ya que cada cuadrado en una fila o columna necesita un color diferente (es decir, las filas y columnas son camarillas ). [1] El número cromático es exactamente n si (es decir, n es uno más o uno menos que un múltiplo de 6). [9]
El número cromático del grafo de una reina es 9. [10]
Un conjunto de vértices es irredundante si al eliminar cualquier vértice del conjunto se modifica la vecindad del conjunto, es decir, para cada vértice, hay un vértice adyacente que no es adyacente a ningún otro vértice del conjunto. Esto corresponde a un conjunto de reinas, cada una de las cuales controla de forma única al menos una casilla. El tamaño máximo IR ( n ) de un conjunto irredundante en el grafo de la reina es difícil de caracterizar; los valores conocidos incluyen [4] : 206–207
Consideremos el juego de persecución-evasión en un grafo de reinas jugado según las siguientes reglas: una reina blanca comienza en una esquina y una reina negra en la esquina opuesta. Los jugadores alternan movimientos, que consisten en mover la reina a un vértice adyacente al que se puede llegar sin pasar por encima (horizontal, vertical o diagonalmente) o aterrizar en un vértice que esté adyacente a la reina opuesta. Este juego puede ser ganado por las blancas con una estrategia de emparejamiento . [11]
