Gráfica del rey

En teoría de grafos , un grafo de rey es un grafo que representa todos los movimientos legales de la pieza de ajedrez del rey en un tablero de ajedrez donde cada vértice representa una casilla en un tablero de ajedrez y cada arista es un movimiento legal. Más específicamente, un grafo de rey es un grafo de rey de un tablero de ajedrez. ^[1] Es el grafo de mapa formado a partir de las casillas de un tablero de ajedrez haciendo un vértice para cada casilla y una arista para cada dos casillas que comparten una arista o una esquina. También se puede construir como el producto fuerte de dos grafos de trayectorias . ^[2] $n\veces m$ $n\veces m$

Para un grafo de rey, el número total de vértices es y el número de aristas es . Para un grafo de rey cuadrado, esto se simplifica de modo que el número total de vértices es y el número total de aristas es . ^[3] $n\veces m$ ${\estilo de visualización nm}$ $Estilo de visualización 4 nm-3(n+m)+2$ $n\veces n$ ${\estilo de visualización n^{2}}$ $(2n-2)(2n-1)$

El vecindario de un vértice en el grafo del rey corresponde al vecindario de Moore para autómatas celulares. ^[4] Una generalización del grafo del rey, llamada grafo del rey , se forma a partir de un cuadrágrafo (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 cuadrátil del cuadrágrafo. ^[5]

En el dibujo de un grafo del rey obtenido a partir de un tablero de ajedrez, hay cruces, pero es posible obtener un dibujo con menos cruces conectando los dos vecinos más cercanos de cada casilla de esquina mediante una curva fuera del tablero de ajedrez en lugar de mediante un segmento de línea diagonal. De esta manera, los cruces son siempre posibles. Para el grafo del rey de tableros de ajedrez pequeños, otros dibujos conducen a incluso menos cruces; en particular, todo grafo del rey es un grafo planar . Sin embargo, cuando tanto y son al menos cuatro, y no son ambos iguales a cuatro, es el número óptimo de cruces. ^[6]^[7] $n\veces m$ $(n-1)(m-1)$ $(n-1)(m-1)-4$ $2\veces n$ ${\estilo de visualización n}$ ${\estilo de visualización m}$ $(n-1)(m-1)-4$

Véase también

Referencias

^ Chang, Gerard J. (1998), "Aspectos algorítmicos de la dominación en grafos", en Du, Ding-Zhu; Pardalos, Panos M. (eds.), Handbook of combinatorial optimality, vol. 3 , Boston, MA: Kluwer Acad. Publ., págs. 339–405, MR 1665419Chang define el gráfico del rey en la pág. 341.
^ Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Dos anticoloraciones de gráficos planos y relacionados" (PDF) , Conferencia internacional de 2005 sobre análisis de algoritmos , Actas de Matemáticas discretas y Ciencias de la computación teórica, Nancy: Asociación de Matemáticas discretas y Ciencias de la computación teórica, págs. 335–341, MR 2193130.
^ Sloane, N. J. A. (ed.). "Secuencia A002943". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
^ Smith, Alvy Ray (1971), "Lenguajes formales bidimensionales y reconocimiento de patrones por autómatas celulares", 12.º Simposio anual sobre conmutación y teoría de autómatas , págs. 144-152, doi :10.1109/SWAT.1971.29.
^ Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), "Problemas de centro y diámetro en triangulaciones y cuadrangulaciones planas", Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '02), págs. 346–355, CiteSeerX 10.1.1.1.7694 , ISBN 0-89871-513-X.
^ Klešč, Marián; Petrillová, Jana; Valo, Matúš (2013), "Número mínimo de cruces en producto fuerte de caminos", Carpathian Journal of Mathematics , 29 (1): 27–32, doi : 10.37193/CJM.2013.01.13 , JSTOR 43999517, MR 3099062
^ Ma, Dengju (2017), "El número de cruce del producto fuerte de dos caminos" (PDF) , The Australasian Journal of Combinatorics , 68 : 35–47, MR 3631655