Grafo do rei

Grafo do rei
Grafo do rei $8\times 8$
vértices	$nm$
arestas	$4nm-3(n+m)+2$
Cintura	$3$ quando $\min(m,n)>1$
Número cromático	$4$ quando $\min(m,n)>1$
Índice cromático	$8$ quando $\min(m,n)>2$

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 $n\times m$ é um grafo do rei de um tabuleiro de xadrez $n\times m$. É 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 $n\times m$ o número total de vértices é $nm$ e o número de arestas é $4nm-3(n+m)+2$. Para um grafo do rei quadrado $n\times n$, o número total de vértices é $n^{2}$ e o número total de arestas é $(2n-2)(2n-1)$.

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.