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

Граф ходов коня
Граф ходов коня 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) даёт размеры шахматных досок, для которых возможен обход конём.

См. также

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