King's graph

EN Texto en inglés Aún no hay artículo en tu idioma: extracto en inglés.

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n × m {\displaystyle n\times m} king's graph is a king's graph of an n × m {\displaystyle n\times m} chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs. For an n × m {\displaystyle n\times m} king's graph the total number of vertices is n m {\displaystyle nm} and the number of edges is 4 n m − 3 ( n + m ) + 2 {\displaystyle 4nm-3(n+m)+2} . For a square n × n {\displaystyle n\times n} king's graph this simplifies so that the total number of vertices is n 2 {\displaystyle n^{2}} and the total number of edges is ( 2 n − 2 ) ( 2 n − 1 ) {\displaystyle (2n-2)(2n-1)} . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata. A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph. In the drawing of a king's graph obtained from an n × m {\displaystyle n\times m} chessboard, there are ( n − 1 ) ( m − 1 ) {\displaystyle (n-1)(m-1)} crossings, but it is possible to obtain a drawing with...