Kong flytte graf

Kong flytte graf
Kong flytte graf 8×8
Toppe	nm
ribben	4 nm - 3( n + m ) + 2

I grafteori er en konges trækgraf en graf, der viser alle mulige træk af kongen på et skakbræt - hvert hjørne svarer til en celle på brættet, og kanter svarer til mulige træk [1] .

For en kongebevægelsesgraf på et bræt af størrelse er antallet af hjørner . For et bræt er antallet af hjørner , og antallet af kanter er . $n \ gange m$ $nm$ $n\ gange n$ $n^{2}$ $(2n-2)(2n-1)$

Området til toppunktet i grafen for kongens bevægelser svarer til Moore-kvarteret i den cellulære automat [2] . En generalisering af kongens bevægelsesgraf kan fås fra en boksgraf (en plan graf, hvor hver flade er en firkant, og hvert indre toppunkt har mindst fire naboer) ved at tilføje to diagonaler for hver firkant [3] .

Se også

Noter

↑ Gerard J. Chang. Håndbog i kombinatorisk optimering, Vol. 3 / Ding-Zhu Du, Panos M. Pardalos. — Boston, MA: Kluwer Acad. Publ., 1998, s. 339-405 . . Chang definerer kongens bevægelsesgraf på side 341 Arkiveret 24. april 2017 på Wayback Machine
↑ Alvy Ray Smith. 12. årlige symposium om koblings- og automatteori. - 1971. - S. 144-152. - doi : 10.1109/SWAT.1971.29 .
↑ Victor Chepoi, Feodor Dragan, Yann Vaxes. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02). - 2002. - S. 346-355 .