Gráfico de movimiento del rey
| Gráfico de movimiento del rey | |
|---|---|
| Gráfico de movimiento del rey 8×8 | |
| picos | Nuevo Méjico |
| costillas | 4 nm - 3( norte + metro ) + 2 |
En la teoría de grafos, el gráfico de movimiento de un rey es un gráfico que representa todos los movimientos posibles del rey en un tablero de ajedrez : cada vértice corresponde a una celda en el tablero y los bordes corresponden a posibles movimientos [1] .
Para un gráfico de movimiento de rey en un tablero de tamaño, el número de vértices es . Para un tablero , el número de vértices es y el número de aristas es .
La vecindad del vértice en la gráfica de movimientos del rey corresponde a la vecindad de Moore del autómata celular [2] . Se puede obtener una generalización del gráfico del movimiento del rey a partir de un gráfico de caja (un gráfico plano en el que cada cara es un cuadrilátero y cada vértice interior tiene al menos cuatro vecinos) sumando dos diagonales para cada cuadrilátero [3] .
Véase también
Notas
- ↑ Gerard J.Chang. manual de optimización combinatoria, vol. 3 / Ding-Zhu Du, Panos M. Pardalos. — Boston, MA: Academia Kluwer. Publ., 1998, págs. 339–405 . . Chang define el gráfico de movimiento del rey en la página 341. Archivado el 24 de abril de 2017 en Wayback Machine .
- ↑ Alvy Ray Smith. 12º Simposio Anual sobre Conmutación y Teoría de Autómatas. - 1971. - S. 144-152. -doi : 10.1109/ SWAT.1971.29 .
- ↑ Víctor Chepoi, Feodor Dragan, Yann Vaxes. Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '02). - 2002. - S. 346-355 .