Királygráf

A matematika, azon belül a gráfelmélet területén egy királygráf (king's graph) olyan gráf, ami a sakkjátékban szereplő király nevű figura lehetséges lépéseit jeleníti meg egy sakktáblán: a csúcsok a sakktábla egy-egy mezőjét jelképezik, az élek pedig a legális lépéseket köztük. Specifikusabban, egy $m\times n$-es királygráf az $m\times n$-es sakktábla királygráfja. A királygráf a sakktábla mezőiből képezett térképgráf, ahol minden mező egy csúcsnak felel meg, és két csúcsot akkor köt össze él, ha a mezőik éle vagy sarka közös. Előállítható két útgráf erős szorzatával.

Királygráf
8×8-as királygráf
Csúcsok száma	nm
Élek száma	$4nm-3(n+m)+2$
Egyéb	összefüggő 2-összefüggő (ha $min(n,m)\geq 2$)

Jellemzése

Minden királygráf 2-összefüggő és rendelkezik Hamilton-körrel az elfajult n=1 vagy m=1 eset kivételével. A négyzetes királygráfok Hamilton-köreinek számát az (A140521 sorozat az OEIS-ben) sorozat, Hamilton-utainak számát az (A158651 sorozat az OEIS-ben) adja meg.

Az $n\times m$-es királygráf csúcsainak száma $nm$, éleinek száma $4nm-3(n+m)+2$. Négyzetes $n\times n$-es királygráf esetében a csúcsok száma $n^{2}$, az élek száma $(2n-2)(2n-1)$, a kromatikus szám 1, ha n=1, 4 ha n≥2; az élkromatikus szám n=2-re 3, n≥3 esetben 8. Az $n\times m$-es királygráf pontosan akkor perfekt, ha $min(n,m)\leq 3.$

Az $n\times n$-es királygráf k hosszúságú köreinek száma az $n\geq 2$ esetben a következő képletekkel fejezhető ki:

$C_{3}=4{(n-1)}^{2}$

$C_{4}=12{(n-1)}^{2}-10(n-1)+1$

$C_{5}=4(n-2)(9n-14)$

$C_{6}=2[63{(n-2)}^{2}-15(n-2)-7].$

Királyprobléma

A királyprobléma egy megoldása.

A királyprobléma azt a kérdést vizsgálja, hogy hány királyt lehet elhelyezni a sakktáblán anélkül, hogy bármelyikük ütésben lenne. A megoldás:

$K_{n}=\left\{{\begin{array}{ll}{\frac {1}{4}}n^{2}&{\mbox{ha n páros}}\,\,\\{\frac {1}{4}}(n+1)^{2}&{\mbox{ha n páratlan}}\,\,\\\end{array}}\right.$

Az, hogy az $n\times m$-es sakktábla minden mezőjének királlyal való támadásához hány királyra van szükség, az $n\times m$-es királygráf dominálási számával egyenlő:

$\gamma (K_{m,n})=\lfloor {\frac {m+2}{3}}\rfloor \lfloor {\frac {n+2}{3}}\rfloor .$

A királygráfban a fokszámok a centrális helyzetű csúcsok 8 értékétől a szélek 5 értékén át a periferikus sarokcsúcsok 3 értékéig terjednek.

A királygráf csúcsainak szomszédsága a sejtautomatáknál használt Moore-szomszédságnak felel meg.

Általánosítása

A királygráf egy általánosítása (kinggraph) négyszöggráfból állítható elő (ez olyan síkgráf, melyben minden korlátos tartomány négyszög alakú, és minden belső csúcsnak legalább négy szomszédja van) úgy, hogy a négyszöggráf minden négyszögű tartományához két átlót adunk.

Kapcsolódó szócikkek

• Bástyagráf
• Futógráf
• Huszárgráf
• Vezérgráf

További információk

• Weisstein, Eric W.: King Graph (angol nyelven). Wolfram MathWorld