Királygráf

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

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 ${\displaystyle m\times n}$-es királygráf az ${\displaystyle m\times n}$-es sakktábla királygráfja.^[1] 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.^[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 ${\displaystyle n\times m}$-es királygráf csúcsainak száma ${\displaystyle nm}$, éleinek száma ${\displaystyle 4nm-3(n+m)+2}$. Négyzetes ${\displaystyle n\times n}$-es királygráf esetében a csúcsok száma ${\displaystyle n^{2}$, az élek száma ${\displaystyle (2n-2)(2n-1)}$,^[3] 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 ${\displaystyle n\times m}$-es királygráf pontosan akkor perfekt, ha ${\displaystyle min(n,m)\leq 3.}$

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

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

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

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

${\displaystyle 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:^[4]

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n\times m}$-es királygráf dominálási számával egyenlő:^[4]

${\displaystyle \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.^[5]

Á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.^[6]

Kapcsolódó szócikkek

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

Jegyzetek

További információk

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