Futógráf

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

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 ${\displaystyle 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 ${\displaystyle n\times n}$-es futógráf k hosszúságú köreinek száma az ${\displaystyle n\geq 2}$ esetben a következő képletekkel fejezhető ki:

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

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

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

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

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 ${\displaystyle 2n-2}$^[2]

Az, hogy az ${\displaystyle 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 ${\displaystyle n\times n}$-es futógráf dominálási számával egyenlő,^[2] ami éppen ${\displaystyle n}$.

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

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