Graficul mișcării Knight

Graficul mișcării Knight
Graficul de mișcare a cavalerului 8 × 8
Vârfurile	nm
coaste	4mn - 6( m + n ) + 8
Circumferinţă	4 (dacă n ≥ 3, m ≥ 5)

În teoria graficelor, un grafic al mișcărilor cavalerului este un grafic care ilustrează toate mișcările posibile ale unui cavaler pe o tablă de șah - fiecare vârf corespunde unei celule de pe tablă, iar marginile corespund mișcărilor posibile [1] .

Pentru un grafic al cavalerului se mișcă pe o tablă de dimensiune, numărul de vârfuri este . Pentru o placă , numărul de vârfuri este , iar numărul de muchii este . $n \ori m$ $nm$ $n\ ori n$ $n^{2}$ $4(n-2)(n-1)$

Găsirea unei căi hamiltoniene pentru graficul de mișcare al cavalerului este problema cavalerul care se plimbă în jurul tablei [1] . Teorema lui Schwenk ( Schwenk ) dă dimensiunile tablelor de șah pentru care cavalerul le poate ocoli [2] .

Vezi și

Note

↑ 1 2 Orin Averbach, Orin Chein. Rezolvarea problemelor prin matematică recreațională. - Dover, 1980. - ISBN 9780486131740 .
↑ John J. Watkins. La nivel general: matematica problemelor tablei de șah. Paradoxuri, nedumeriri și enigme matematice pentru zgârietorii serioși de cap. - Princeton University Press, 2012. - P. 44 . — ISBN 9780691154985 .