Futógráf

Sablon:Gráf infobox 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 – az 1×n-es eset kivételével, ahol $n\ne 2$ – 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\ge 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

Sablon:Sakkdiagram 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

• Sablon:MathWorld
• Sablon:MathWorld