Граф ходів коня

У теорії графів граф ходів коня — граф, що зображує всі можливі ходи коня на шахівниці; кожна вершина відповідає клітинці дошки, а ребра — можливим ходам.

Граф ходів коня
Граф ходів коня 8 × 8
Вершин	nm
Ребер	4mn - 6(m + n) + 8
Обхват	4 (якщо n ≥ 3, m ≥ 5)
Властивості	двочастковий

Для графа ходів коня на дошці розміру ${\displaystyle n\times m}$ число вершин дорівнює ${\displaystyle nm}$. Для дошки ${\displaystyle n\times n}$ число вершин дорівнює ${\displaystyle n^{2}}$, а число ребер дорівнює ${\displaystyle 4(n-2)(n-1)}$.

Знаходження гамільтонового шляху для графа ходів коня — це завдання про обхід дошки конем. Теорема Швенка (Schwenk) дає розміри шахових дощок, для яких можливий обхід конем.

Див. також

• Граф решітки
• Туровий граф
•  

Примітки

1. Orin Averbach, Orin Chein. Problem Solving Through Recreational Mathematics. — Dover, 1980. — .
2. John J. Watkins. Across the Board: The Mathematics of Chessboard Problems. Paradoxes, perplexities, and mathematical conundrums for the serious head scratcher. — Princeton University Press, 2012. — С. 44. — .