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

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

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

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

Див. також

• Граф ходів короля
• Граф решітки
• Туровий граф
• Шаблон:Portal-inline