В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам.
Для графа ходов коня на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется .
Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём.
См. также Граф ходов короля Граф решётки Ладейный граф
Примечания
Категория:Параметрические семейства графов