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

В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам.

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

Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём.

См. также

• Граф ходов короля
• Граф решётки
• Ладейный граф