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

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

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

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

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

• Граф ходів короля
• Граф решітки
• Туровий граф
•   Портал «Шахи»