WikiSort.ru - Не сортированное

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

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

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

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

См. также

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

Примечания