En teoría de grafos , el gráfico de un rey es un gráfico que representa todos los movimientos legales de la pieza de ajedrez del 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 la gráfica del rey es la gráfica de un rey de un tablero de ajedrez. [1] Es el gráfico de mapa formado a partir 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 trayectoria . [2]
Gráfico del rey | |
---|---|
Vértices | |
Bordes | |
Circunferencia | Cuándo |
Número cromático | Cuándo |
Índice cromático | Cuándo |
Tabla de gráficos y parámetros |
Por un gráfica del rey el número total de vértices es y el número de aristas es . Por un cuadrado la gráfica del rey esto se simplifica de modo que el número total de vértices es y el número total de aristas es . [3]
La vecindad de un vértice en el gráfico del rey corresponde a la vecindad de Moore para autómatas celulares. [4] Una generalización de la gráfica del rey, llamado un kinggraph , se forma a partir de un grafo cuadrado (un gráfico plana en la que cada cara acotada es un cuadrilátero y cada vértice interior tiene al menos cuatro vecinos) mediante la adición de las dos diagonales de cada cara cuadrilátero del gráfico cuadrado. [5]
Ver también
Referencias
- ^ Chang, Gerard J. (1998), "Aspectos algorítmicos de la dominación en los gráficos", en Du, Ding-Zhu; Pardalos, Panos M. (eds.), Manual de optimización combinatoria, vol. 3 , Boston, MA: Kluwer Acad. Publ., Págs. 339–405, MR 1665419. Chang define la gráfica del rey en la p. 341 .
- ^ Berend, Daniel; Coré, Efraín; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF) , 2005 International Conference on Analysis of Algorithms , Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, págs. 335–341, MR 2193130.
- ^ Sloane, N. J. A. (ed.). "Secuencia A002943" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Smith, Alvy Ray (1971), "Lenguajes formales bidimensionales y reconocimiento de patrones por autómatas celulares", 12º Simposio anual sobre la teoría de la conmutación y los 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.