Vezérgráf

Sablon:Gráf infobox 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(mod6)$ 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 Sablon:OEIS adja meg.

A négyzetes vezérgráfok Hamilton-köreinek számát az Sablon:OEIS, Hamilton-utainak számát az Sablon:OEIS adja meg.

Vezérprobléma

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 Sablon:OEIS 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 Sablon:OEIS listázza.

Kapcsolódó szócikkek

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

További információk

• Sablon:MathWorld
• Sablon:MathWorld
• Sablon:MathWorld