Na teoria dos grafos, um grafo do rei é um grafo que representa todos os movimentos legais da peça de xadrez do rei em um tabuleiro de xadrez, onde cada vértice representa um quadrado em um tabuleiro de xadrez e cada borda é um movimento legal. Mais especificamente, um grafo do rei é um grafo do rei de um tabuleiro de xadrez .. Chang defines the king's graph on p. 341. É o grafo mapa formado a partir dos quadrados de um tabuleiro de xadrez, fazendo um vértice para cada quadrado e uma borda para cada dois quadrados que compartilham uma borda ou um canto. Também pode ser construído como o produto forte de dois grafos caminho..
Para um grafo do rei o número total de vértices é e o número de arestas é . Para um grafo do rei quadrado , o número total de vértices é e o número total de arestas é .
A vizinhança de um vértice no grafo do rei corresponde à vizinhança de Moore para autômato celular.. Uma generalização do grafo do rei, chamada de kinggraph, é formada a partir de um grafo quadrado pela adição de duas diagonais de cada face quadrilateral do grafo quadrado..
Categoria:Matemática sobre xadrez Categoria:Teoria dos grafos