Lovagmozgás grafikonja

Lovagmozgás grafikonja
Lovagmozgás grafikonja 8 × 8
Csúcsok	nm
borda	4 perc - 6( m + n ) + 8
Heveder	4 (ha n ≥ 3, m ≥ 5)

A gráfelméletben a lovagok lépéseinek gráfja egy olyan gráf, amely egy lovag összes lehetséges lépését ábrázolja a sakktáblán – minden csúcs a tábla egy cellájának felel meg, az élek pedig a lehetséges lépéseknek [1] .

A lovagok mozgását ábrázoló grafikon esetén a csúcsok száma . Egy tábla esetén a csúcsok száma , az élek száma pedig . $n \szer m$ $nm$ $n\szer n$ $n^{2}$ $4(n-2)(n-1)$

A lovag mozgásgráfjának Hamilton-útvonalának megtalálása a tábla körül sétáló lovag problémája [1] . Schwenk tétele ( Schwenk ) megadja azoknak a sakktábláknak a méreteit, amelyeknél a lovag megkerülheti [2] .

Lásd még

Jegyzetek

↑ 1 2 Orin Averbach, Orin Chein. Problémamegoldás a szabadidős matematikán keresztül. - Dover, 1980. - ISBN 9780486131740 .
↑ John J. Watkins. Az egész fórumon: A sakktábla-feladatok matematikája. Paradoxonok, zavarok és matematikai fejtörések a komoly fejvakarók számára. - Princeton University Press, 2012. - 44. o . — ISBN 9780691154985 .