В теории графов граф коня или граф хода коня — это граф , который представляет все допустимые ходы шахматной фигуры коня на шахматной доске . Каждая вершина этого графа представляет собой клетку шахматной доски, а каждое ребро соединяет две клетки, находящиеся на расстоянии хода коня друг от друга. Точнее, граф коня — это граф коня шахматной доски. [1] Его вершины могут быть представлены как точки евклидовой плоскости , декартовы координаты которых являются целыми числами с и (точки в центрах квадратов шахматной доски), а также как две вершины, соединенные ребром, когда их евклидово расстояние равно .
Для графа рыцаря число вершин равно . Если и то количество ребер равно (иначе ребер нет). Для рыцарского графа они упрощаются так, что количество вершин равно , а количество ребер равно . [2]
Гамильтонов цикл на графе коня представляет собой (замкнутое) путешествие коня . [1] Шахматная доска с нечетным числом клеток не имеет обхода, поскольку граф коня представляет собой двудольный граф (каждый цвет клеток может использоваться как один из двух независимых наборов , а ходы коня всегда меняют цвет поля) и только двудольные графы с четным числом вершин могут иметь гамильтоновы циклы. На большинстве шахматных досок с четным количеством полей есть ход коня; Теорема Швенка дает точный список того, какие из них подходят, а какие нет. [3]
Когда он модифицирован так, чтобы иметь тороидальные граничные условия (это означает, что конь не блокируется краем доски, а вместо этого продолжает движение на противоположный край), граф коня аналогичен четырехмерному графу гиперкуба . [3]
