Gráfico de Bishop

En matemáticas, un grafo de alfil es un grafo que representa todos los movimientos legales de la pieza de ajedrez, el alfil, en un tablero de ajedrez . Cada vértice representa una casilla del tablero y cada arista representa un movimiento legal del alfil; es decir, hay una arista entre dos vértices (casillas) si ocupan una diagonal común. Cuando el tablero de ajedrez tiene dimensiones${\displaystyle m\times n}$, entonces el gráfico inducido se llama${\displaystyle m\times n}$gráfico del obispo.

El hecho de que el tablero de ajedrez tenga casillas de dos colores, digamos rojo y negro, de modo que las casillas adyacentes horizontal o verticalmente tengan colores opuestos, implica que el grafo del alfil tiene dos componentes conexas, cuyos conjuntos de vértices son las casillas rojas y negras, respectivamente. La razón es que los movimientos diagonales del alfil no le permiten cambiar de color, pero mediante uno o más movimientos puede pasar de cualquier casilla a cualquier otra del mismo color. ^{[ 1 ]} Las dos componentes son isomorfas si el tablero tiene un lado de longitud par, pero no si ambos lados son impares.

Un componente del gráfico del alfil puede tratarse como un gráfico de la torre en un rombo si el tablero original es cuadrado y tiene lados de longitud impar, porque si las casillas rojas (por ejemplo) se giran 45 grados, los movimientos del alfil se vuelven horizontales y verticales, al igual que los de la torre . ^{[ 2 ]}

Se dice que un alfil ataca una casilla si puede llegar a ella en un solo movimiento. Un conjunto dominante es una disposición de alfiles tal que cada casilla es atacada u ocupada por uno de ellos. Un conjunto dominante independiente es aquel en el que ningún alfil ataca a otro. El número mínimo de alfiles necesarios para dominar un tablero cuadrado de lado n es exactamente n , y este es también el número mínimo de alfiles que pueden formar un conjunto dominante independiente. Por el contrario, un conjunto de dominación total, que es aquel en el que cada casilla, incluidas las ocupadas por alfiles, es atacada por uno de ellos, requiere más alfiles; en el tablero cuadrado de lado n ≥ 3, el tamaño mínimo de un conjunto dominante total es${\displaystyle 2\lceil 2(n-1)/3\rceil ,}$aproximadamente 1/3 más grande que un conjunto dominante mínimo. ^{[ 3 ] [ 4 ]}