Vezérgráf

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 ${\displaystyle m\times n}$-es vezérgráf az ${\displaystyle m\times n}$-es sakktábla vezérgráfja.^[1]

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

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

Mivel az ${\displaystyle 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 ${\displaystyle n\equiv 1,5(mod\ 6)}$ esetben n szín elégséges is a színezéshez. Az ${\displaystyle 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.

Bővebben: Nyolckirálynő-probléma

A vezérprobléma azt a kérdést vizsgálja, hogy hány vezért lehet elhelyezni az ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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

Jegyzetek

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