Král pohybový graf

Král pohybový graf
Graf pohybu krále 8×8
Vrcholy	nm
žebra	4 nm - 3 ( n + m ) + 2

V teorii grafů je grafem tahu krále graf zobrazující všechny možné tahy krále na šachovnici — každý vrchol odpovídá buňce na šachovnici a hrany odpovídají možným tahům [1] .

Pro královský pohybový graf na desce o velikosti je počet vrcholů . U desky je počet vrcholů a počet hran je . $n \krát m$ $nm$ $n\krát n$ $n^{2}$ $(2n-2)(2n-1)$

Okolí vrcholu v grafu tahů krále odpovídá Moorovu okolí buněčného automatu [2] . Zobecnění grafu tahu krále lze získat z krabicového grafu (rovinný graf, kde každá plocha je čtyřúhelník a každý vnitřní vrchol má alespoň čtyři sousedy) přidáním dvou úhlopříček pro každý čtyřúhelník [3] .

Viz také

Poznámky

↑ Gerard J. Chang. Příručka kombinatorické optimalizace, sv. 3 / Ding-Zhu Du, Panos M. Pardalos. — Boston, MA: Kluwer Acad. Publ., 1998, s. 339–405 . . Chang definuje graf pohybu krále na straně 341 Archivováno 24. dubna 2017 na Wayback Machine
↑ Alvy Ray Smith. 12. ročník sympozia o spínání a teorii automatů. - 1971. - S. 144-152. - doi : 10.1109/SWAT.1971.29 .
↑ Victor Chepoi, Feodor Dragan, Yann Vaxes. Sborník příspěvků z třináctého výročního sympozia ACM-SIAM o diskrétních algoritmech (SODA '02). - 2002. - S. 346-355 .