Меню Главная Случайная статья Настройки Граф ходов коня Материал из https://ru.wikipedia.org В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам[1]. Для графа ходов коня на доске размера ${\displaystyle n\times m}$ число вершин равняется ${\displaystyle nm}$. Для доски ${\displaystyle n\times n}$ число вершин равняется ${\displaystyle n^{2}}$, а число рёбер равняется ${\displaystyle 4(n-2)(n-1)}$. Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём[1]. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём[2]. См. также Граф ходов короля Граф решётки Ладейный граф Примечания 1 2 Orin Averbach, Orin Chein. Problem Solving Through Recreational Mathematics. — Dover, 1980. — ISBN 9780486131740. 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.