Kung flytta graf

Kung flytta graf
Kung flytta graf 8×8
Toppar	nm
revben	4 nm - 3( n + m ) + 2

I grafteorin är en kungens draggraf en graf som visar alla möjliga drag av kungen på ett schackbräde - varje hörn motsvarar en cell på brädet, och kanter motsvarar möjliga drag [1] .

För en kungflyttningsgraf på en bräda av storlek är antalet hörn . För en bräda är antalet hörn , och antalet kanter är . $n \ gånger m$ $nm$ $n\ gånger n$ $n^{2}$ $(2n-2)(2n-1)$

Området för vertexet i grafen över kungens rörelser motsvarar Moore-området för den cellulära automaten [2] . En generalisering av kungens rörelsegraf kan erhållas från en boxgraf (en plan graf där varje yta är en fyrhörning och varje inre vertex har minst fyra grannar) genom att lägga till två diagonaler för varje fyrhörning [3] .

Se även

Anteckningar

↑ Gerard J. Chang. Handbok för kombinatorisk optimering, vol. 3 / Ding-Zhu Du, Panos M. Pardalos. — Boston, MA: Kluwer Acad. Publ., 1998, s. 339–405 . . Chang definierar kungens rörelsegraf på sidan 341 Arkiverad 24 april 2017 på Wayback Machine
↑ Alvy Ray Smith. 12:e årliga symposiet om omkopplings- och automatteori. - 1971. - S. 144-152. - doi : 10.1109/SWAT.1971.29 .
↑ Victor Chepoi, Feodor Dragan, Yann Vaxes. Uppdrag från det trettonde årliga ACM-SIAM-symposiet om diskreta algoritmer (SODA '02). - 2002. - S. 346-355 .