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

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

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

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

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

Див. також

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