A matematika, azon belül a gráfelmélet területén egy vezérgráf (queen's graph) olyan gráf, ami a sakkjátékban szereplő vezé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 vezérgráf az -es sakktábla vezérgráfja..
Jellemzése Minden vezérgráf 2-összefüggő és rendelkezik Hamilton-körrel az elfajult n=1 vagy m=1 eset kivételével. A vezérgráf speciális esete az -es sakktáblán a teljes gráf.
A perfekt vezérgráfok közé tartoznak az -es, -es és -as vezérgráfok.
Mivel az -es vezérgráf minden sora és oszlopa n-klikk, ezen gráfok kromatikus száma legalább n. Belátható, hogy az esetben n szín elégséges is a színezéshez. Az -es vezérgráfok kromatikus számát az adja meg.
A négyzetes vezérgráfok Hamilton-köreinek számát az , Hamilton-utainak számát az adja meg.
Vezérprobléma
A vezérprobléma azt a kérdést vizsgálja, hogy hány vezért lehet elhelyezni az -es sakktáblán anélkül, hogy bármelyikük ütésben lenne. A megoldást a adja meg.
Az, hogy az -es sakktábla minden mezőjének vezérrel való támadásához hány vezérre van szükség, az -es vezérgráf dominálási számával egyenlő, ami a 8×8-as sakktáblán 5, egyébként a megoldást a listázza.
Kapcsolódó szócikkek Bástyagráf Futógráf Huszárgráf Királygráf
Jegyzetek
További információk
Kategória:Sakk Kategória:Parametrikus gráfcsaládok