Huszárgráf

Huszárgráf
8×8-as huszárgráf
Csúcsok száma	nm
Élek száma	${\displaystyle 4mn-6(m+n)+8}$ (ha min(n, m) ≥ 2)
Átmérő	2
Derékbőség	4 (ha ${\displaystyle n\geq 3}$ és ${\displaystyle m\geq 5}$)
Egyéb	páros

A matematika, azon belül a gráfelmélet területén egy huszárgráf (knight's graph) olyan gráf, ami a sakkjátékban szereplő huszár 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 huszárgráf az ${\displaystyle m\times n}$-es sakktábla huszárgráfja.^[1] Csúcsai felfoghatók az euklideszi sík azon pontjaiként, melyek Descartes-koordinátái (a sakktábla mezőinek középpontjai) ${\displaystyle (x,y)}$ ${\displaystyle 1\leq x\leq m}$ és ${\displaystyle 1\leq y\leq n}$ egész számok, és két csúcsot akkor köt össze él, ha euklideszi távolságuk éppen ${\displaystyle {\sqrt {5}}}$.

Jellemzői

A huszárgráfban a fokszámok a centrális helyzetű csúcsok 8 értékétől a legperiferikusabb sarokcsúcsok 2 értékéig terjednek.

A huszárgráf a sakkfigurák gráfjai között (bástyagráf, futógráf, királygráf, vezérgráf) egyetlenként páros gráf.

A huszárgráfnak az elfajult 1×n esetben (üres gráf) n, 2×n esetben 4, 3×3 esetben 2 összefüggő komponense van; 3×3-asnál nagyobb sakktáblákon mindig összefüggő.

Az ${\displaystyle m\times n}$-es huszárgráf csúcsainak száma ${\displaystyle nm}$. A négyzetes, ${\displaystyle n\times n}$-es huszárgráf csúcsainak száma ${\displaystyle n^{2}}$, éleinek száma pedig ${\displaystyle 4(n-2)(n-1)}$.^[2]

Az ${\displaystyle n\times n}$-es huszárgráf k hosszúságú köreinek száma páratlan k-kra 0, k=4 hosszúságú körökre pedig a következő képlet adja meg értékét:^[3]

${\displaystyle C_{4}=\left\{{\begin{array}{ll}0&{\mbox{ha}}\,\,n\leq 3\\2(3n^{2}-18n+26)&{\mbox{egyébként}}\,\,\\\end{array}}\right.}$

Ha a sakktáblából „széleinek összeragasztásával” tóruszt készítünk (tehát a tábla egyik szélén kilépve a másik szélén lépünk be), a ${\displaystyle 4\times 4}$-es huszárgráf megegyezik a négydimenziós hiperkockagráffal.^[4]

Huszárvándorlás

Bővebben: Huszárvándorlás-probléma

A huszárgráf Hamilton-körét vagy Hamilton-útját zárt, illetve nyitott huszárvándorlásnak nevezik.^[1] A zárt huszárkörút páratlan számú mezővel rendelkező sakktáblákon nem lehetséges, hiszen a huszárgráf páros, és csak a páros számú csúccsal rendelkező páros gráfoknak lehet Hamilton-köre. A Schwenk-tétel pontosan listázza, hogy mely sakktáblákon létezik zárt huszárkörút, és melyeken nem.^[4]

Kapcsolódó szócikkek

• Bástyagráf
• Futógráf
• Királygráf
• Vezérgráf

Jegyzetek

További információk

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