Futógráf

Futógráf
Csúcsok száma	nm
Egyéb	perfekt

A matematika, azon belül a gráfelmélet területén egy futógráf (bishop's graph) olyan gráf, ami a sakkjátékban szereplő futó 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 futógráf az $m\times n$-es sakktábla futógráfja.

Jellemzése

Mivel a futók vagy a sakktábla világos, vagy a sötét mezőin haladnak, és átlós mozgásuk miatt nem váltanak színt, ezért a triviális 1×1-es sakktábla kivételével egyetlen futógráf sem összefüggő, hanem 2 összefüggő komponens alkotja. A futógráf speciális esetei az 1×n-es sakktáblán az üres gráf, a 2×n-es sakktáblán két diszjunkt, n hosszúságú útgráf uniója.

Az $m\times n$-es futógráfot alkotó, világos és sötét futógráfnak is nevezett két komponens izomorf, kivéve, ha n és m is páratlan (ilyenkor a világos és sötét mezők száma nem egyezik).

Az $n\times n$-es futógráf k hosszúságú köreinek száma az $n\geq 2$ esetben a következő képletekkel fejezhető ki:

$C_{3}={\frac {1}{6}}(n-2){(n-1)}^{2}n$

$C_{4}={\frac {1}{30}}(n-2)(n-1)n(3n^{2}-11n+11)$

$C_{5}=4(n-2)(9n-14)$

$C_{6}=2[63{(n-2)}^{2}-15(n-2)-7].$

Futóprobléma

A futóprobléma egy megoldása.

A futóprobléma azt a kérdést vizsgálja, hogy hány futót lehet elhelyezni az n×n-es sakktáblán anélkül, hogy bármelyikük ütésben lenne. A megoldás $2n-2$

Az, hogy az $n\times n$-es sakktábla minden mezőjének futóval való támadásához hány futóra van szükség, az $n\times n$-es futógráf dominálási számával egyenlő, ami éppen $n$.

Kapcsolódó szócikkek

• Bástyagráf
• Huszárgráf
• Királygráf
• Vezérgráf

További információk

• Weisstein, Eric W.: Bishop Graph (angol nyelven). Wolfram MathWorld
• Weisstein, Eric W.: Bishops Problem (angol nyelven). Wolfram MathWorld