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