Граф ходов коня (Ijgs ]k;kf tkux)

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

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

Для графа ходов коня на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется .

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

Примечания

[править | править код]
  1. 1 2 Orin Averbach, Orin Chein. Problem Solving Through Recreational Mathematics. — Dover, 1980. — ISBN 9780486131740.
  2. John J. Watkins. Across the Board: The Mathematics of Chessboard Problems. Paradoxes, perplexities, and mathematical conundrums for the serious head scratcher. — Princeton University Press, 2012. — С. 44. — ISBN 9780691154985.