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 -es futógráf az -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 – 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 -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 -es futógráf k hosszúságú köreinek száma az esetben a következő képletekkel fejezhető ki:
Futóprobléma
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 Bishop’s problem
Az, hogy az -es sakktábla minden mezőjének futóval való támadásához hány futóra van szükség, az -es futógráf dominálási számával egyenlő, ami éppen .
Kapcsolódó szócikkek Bástyagráf Huszárgráf Királygráf Vezérgráf
Jegyzetek
További információk
Kategória:Sakk Kategória:Parametrikus gráfcsaládok