Huszárgráf

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 $m\times n$-es huszárgráf az $m\times n$-es sakktábla huszárgráfja. Csúcsai felfoghatók az euklideszi sík azon pontjaiként, melyek Descartes-koordinátái (a sakktábla mezőinek középpontjai) $(x,y)$ $1\leq x\leq m$ és $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 ${\sqrt {5}}$.

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

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 $m\times n$-es huszárgráf csúcsainak száma $nm$. A négyzetes, $n\times n$-es huszárgráf csúcsainak száma $n^{2}$, éleinek száma pedig $4(n-2)(n-1)$.

Az $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:

$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 $4\times 4$-es huszárgráf megegyezik a négydimenziós hiperkockagráffal.

Huszárvándorlás

A huszárgráf Hamilton-körét vagy Hamilton-útját zárt, illetve nyitott huszárvándorlásnak nevezik. 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.

Kapcsolódó szócikkek

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

További információk

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