Vezérgráf

Vezérgráf
Csúcsok száma	nm

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 $m\times n$-es vezérgráf az $m\times n$-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 $1\times n$-es sakktáblán a $K_{n}$ teljes gráf.

A perfekt vezérgráfok közé tartoznak az $1\times n$-es, $2\times n$-es és $3\times 3$-as vezérgráfok.

Mivel az $n\times n$-es vezérgráf minden sora és oszlopa n-klikk, ezen gráfok kromatikus száma legalább n. Belátható, hogy az $n\equiv 1,5(mod\ 6)$ esetben n szín elégséges is a színezéshez. Az $n\times n$-es vezérgráfok kromatikus számát az (A088202 sorozat az OEIS-ben) adja meg.

A négyzetes vezérgráfok Hamilton-köreinek számát az (A158663 sorozat az OEIS-ben), Hamilton-utainak számát az (A158664 sorozat az OEIS-ben) adja meg.

Vezérprobléma

A vezérprobléma egy megoldása.

A vezérprobléma azt a kérdést vizsgálja, hogy hány vezért lehet elhelyezni az $n\times n$-es sakktáblán anélkül, hogy bármelyikük ütésben lenne. A megoldást a (A000170 sorozat az OEIS-ben) adja meg.

Az, hogy az $n\times n$-es sakktábla minden mezőjének vezérrel való támadásához hány vezérre van szükség, az $n\times n$-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 (A075458 sorozat az OEIS-ben) listázza.

Kapcsolódó szócikkek

• Bástyagráf
• Futógráf
• Huszárgráf
• Királygráf

További információk

• Weisstein, Eric W.: Queen Graph (angol nyelven). Wolfram MathWorld
• Weisstein, Eric W.: Queen’s Graph (angol nyelven). Wolfram MathWorld
• Weisstein, Eric W.: Queen’s Problem (angol nyelven). Wolfram MathWorld