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

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

Граф ходов коня
Граф ходов коня 8 × 8
Вершин	nm
Рёбер	4mn - 6(m + n) + 8
Обхват	4 (если n ≥ 3, m ≥ 5)

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

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

См. также Править

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