Huszárgráf

Huszárgráf
8×8-as huszárgráf
8×8-as huszárgráf

Csúcsok számanm
Élek száma (ha min(n, m) ≥ 2)
Átmérő2
Derékbőség4 (ha és )
Egyébpá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 -es huszárgráf az -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) és egész számok, és két csúcsot akkor köt össze él, ha euklideszi távolságuk éppen .

Jellemzői

a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
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 -es huszárgráf csúcsainak száma . A négyzetes, -es huszárgráf csúcsainak száma , éleinek száma pedig .[2]

Az -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]

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

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.[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

Jegyzetek

További információk