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.. 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 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 .
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:E. Weisstein, Nov. 16, 2014
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.
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
Jegyzetek
További információk
Kategória:Sakk Kategória:Parametrikus gráfcsaládok