Huszárgráf

Sablon:Gráf infobox 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\le x\le m$ és $1\le y\le n$ egész számok, és két csúcsot akkor köt össze él, ha euklideszi távolságuk éppen $\sqrt{5}$.

Jellemzői

Sablon:SakkdiagramA 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=\{\begin{array}{cc}0& \text{ha}n\le 3\\ 2(3n^2-18n+26)& \text{egyébként}\end{array}$

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

Sablon:Fő 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

• Sablon:MathWorld