A matematika, azon belül a gráfelmélet területén egy királygráf (king's graph) olyan gráf, ami a sakkjátékban szereplő király 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 királygráf az -es sakktábla királygráfja.. Chang itt definiálja a királygráfokat: p. 341. A királygráf a sakktábla mezőiből képezett térképgráf, ahol minden mező egy csúcsnak felel meg, és két csúcsot akkor köt össze él, ha a mezőik éle vagy sarka közös. Előállítható két útgráf erős szorzatával..
Jellemzése Minden királygráf 2-összefüggő és rendelkezik Hamilton-körrel az elfajult n=1 vagy m=1 eset kivételével. A négyzetes királygráfok Hamilton-köreinek számát az sorozat, Hamilton-utainak számát az adja meg.
Az -es királygráf csúcsainak száma , éleinek száma . Négyzetes -es királygráf esetében a csúcsok száma , az élek száma , a kromatikus szám 1, ha n=1, 4 ha n≥2; az élkromatikus szám n=2-re 3, n≥3 esetben 8. Az -es királygráf pontosan akkor perfekt, ha
Az -es királygráf k hosszúságú köreinek száma az esetben a következő képletekkel fejezhető ki:
Királyprobléma
A királyprobléma azt a kérdést vizsgálja, hogy hány királyt lehet elhelyezni a sakktáblán anélkül, hogy bármelyikük ütésben lenne. A megoldás:King’s problem
Az, hogy az -es sakktábla minden mezőjének királlyal való támadásához hány királyra van szükség, az -es királygráf dominálási számával egyenlő:
A királygráf csúcsainak szomszédsága a sejtautomatáknál használt Moore-szomszédságnak felel meg..
Általánosítása A királygráf egy általánosítása (kinggraph) négyszöggráfból állítható elő (ez olyan síkgráf, melyben minden korlátos tartomány négyszög alakú, és minden belső csúcsnak legalább négy szomszédja van) úgy, hogy a négyszöggráf minden négyszögű tartományához két átlót adunk..
Kapcsolódó szócikkek Bástyagráf Futógráf Huszárgráf Vezérgráf
Jegyzetek
További információk
Kategória:Sakk Kategória:Parametrikus gráfcsaládok