Kuninkaan siirtokaavio

Kuninkaan siirtokaavio
Kuninkaan siirtokaavio 8×8
Huiput	nm
kylkiluut	4 nm - 3( n + m ) + 2

Graafiteoriassa kuninkaan siirtograafi on graafi, joka kuvaa kaikki mahdolliset kuninkaan liikkeet shakkilaudalla – jokainen kärki vastaa laudan solua ja reunat vastaavat mahdollisia liikkeitä [1] .

Kuninkaan siirtokaavion kokoisella laudalla pisteiden määrä on . Lautassa kärkien lukumäärä on ja reunojen määrä on . $n \ kertaa m$ $nm$ $n\ kertaa n$ $n^{2}$ ${\näyttötyyli (2n-2)(2n-1)}$

Kuninkaan liikkeiden kuvaajassa olevan kärjen naapurusto vastaa soluautomaatin Mooren naapurustoa [2] . Kuninkaan liikegraafin yleistys voidaan saada laatikkograafista (tasograafi, jossa jokainen pinta on nelikulmio ja jokaisella sisäpisteellä on vähintään neljä naapuria) lisäämällä kaksi diagonaalia jokaiselle nelikulmiolle [3] .

Katso myös

Muistiinpanot

↑ Gerard J. Chang. Handbook of kombinatorical optimization, Voi. 3 / Ding-Zhu Du, Panos M. Pardalos. — Boston, MA: Kluwer Acad. Publ., 1998, s. 339-405 . . Chang määrittelee kuninkaan siirtokaavion sivulla 341 Arkistoitu 24. huhtikuuta 2017 Wayback Machinessa
↑ Alvy Ray Smith. 12. vuotuinen symposium vaihtamisesta ja automaatioteoriasta. - 1971. - S. 144-152. - doi : 10.1109/SWAT.1971.29 .
↑ Victor Chepoi, Feodor Dragan, Yann Vaxes. Kolmentoista vuotuisen ACM-SIAM-symposiumin julkaisut diskreetistä algoritmista (SODA '02). - 2002. - S. 346-355 .