Grafo do rei

Grafo do rei
Grafo do rei ${\displaystyle 8\times 8}$
vértices	${\displaystyle nm}$
arestas	${\displaystyle 4nm-3(n+m)+2}$
Cintura	${\displaystyle 3}$ quando ${\displaystyle \min(m,n)>1}$
Número cromático	${\displaystyle 4}$ quando ${\displaystyle \min(m,n)>1}$
Índice cromático	${\displaystyle 8}$ quando ${\displaystyle \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 ${\displaystyle n\times m}$ é um grafo do rei de um tabuleiro de xadrez ${\displaystyle n\times m}$.^[1] É 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.^[2]

Para um grafo do rei ${\displaystyle n\times m}$ o número total de vértices é ${\displaystyle nm}$ e o número de arestas é ${\displaystyle 4nm-3(n+m)+2}$. Para um grafo do rei quadrado ${\displaystyle n\times n}$, o número total de vértices é ${\displaystyle n^{2}}$ e o número total de arestas é ${\displaystyle (2n-2)(2n-1)}$.^[3]

A vizinhança de um vértice no grafo do rei corresponde à vizinhança de Moore para autômato celular.^[4] 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.^[5]