Saltar para o conteúdo

Grafo do rei

Origem: Wikipédia, a enciclopédia livre.
Grafo do rei

Grafo do rei
vértices
arestas
Cintura quando
Número cromático quando
Índice cromático quando

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 .[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 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 é .[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]

Referências

  1. Chang, Gerard J. (1998), «Algorithmic aspects of domination in graphs», in: Du, Ding-Zhu; Pardalos, Panos M., Handbook of combinatorial optimization, Vol. 3, Boston, MA: Kluwer Acad. Publ., pp. 339–405, MR 1665419 . Chang defines the king's graph on p. 341.
  2. Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), «Two-anticoloring of planar and related graphs» (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130 .
  3. Sloane, N. J. A. (ed.). «Sequência A002943». On-Line Encyclopedia of Integer Sequences (em inglês). OEIS Foundation 
  4. Smith, Alvy Ray (1971), «Two-dimensional formal languages and pattern recognition by cellular automata», 12th Annual Symposium on Switching and Automata Theory, pp. 144–152, doi:10.1109/SWAT.1971.29 .
  5. Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), «Center and diameter problems in plane triangulations and quadrangulations», Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), ISBN 0-89871-513-X, pp. 346–355 .