Királygráf

Sablon:Gráf infobox 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.

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 Sablon:OEIS sorozat, Hamilton-utainak számát az Sablon:OEIS 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)\le 3.$

Az $n\times n$-es királygráf k hosszúságú köreinek száma az $n\ge 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

Sablon:Sakkdiagram 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=\{\begin{array}{cc}\frac{1}{4}{n}^2& \text{ha n páros}\\ \frac{1}{4}(n+1{)}^2& \text{ha n páratlan}\end{array}$

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á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

• Sablon:MathWorld