В теории графов , в расстоянии графа рыцарского или графе тура рыцаря , является графиком , который представляет все юридические хода рыцаря шахмат куска на шахматной доске . Каждая вершина этого графа представляет собой квадрат шахматной доски, а каждое ребро соединяет два квадрата, которые являются ходом коня друг от друга. В частности, граф рыцаря - граф рыцаря шахматная доска. [1] Его вершины можно представить как точки евклидовой плоскости , декартовы координаты которых целые числа с а также (точки в центрах квадратов шахматной доски) и с двумя вершинами, соединенными ребром, когда их евклидово расстояние равно.
Граф рыцаря | |
---|---|
Вершины | |
Края | (если а также ) |
Обхват | 4 (если а также ) |
Характеристики | двудольный |
Таблица графиков и параметров |
Для графа рыцаря, количество вершин . Если а также то количество ребер равно (иначе нет ребер). Для графа рыцаря, они упрощаются, так что количество вершин равно а количество ребер равно . [2]
Гамильтонов цикл на графике рыцаря (замкнутый) тур рыцаря . [1] Шахматная доска с нечетным числом квадратов не имеет обхода, потому что граф коня является двудольным графом и только двудольные графы с четным числом вершин могут иметь гамильтоновы циклы. Все, кроме конечного числа шахматных досок с четным числом клеток, имеют ход коня; Теорема Швенка дает точный список того, какие из них работают, а какие нет. [3]
Когда он изменен, чтобы иметь тороидальные граничные условия (это означает, что конь не блокируется краем доски, а вместо этого продолжает движение на противоположном крае),граф Найта такой же, как граф четырехмерного гиперкуба . [3]
Смотрите также
Рекомендации
- ^ a b Авербах, Бонни; Чейн, Орин (1980), Решение проблем с помощью развлекательной математики , Довер, стр. 195, ISBN 9780486131740.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A033996» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ а б Уоткинс, Джон Дж. (2004), Через доску: Математика задач на шахматной доске. Парадоксы, затруднения и математические головоломки для серьезного царапающего голову , Princeton University Press, стр. 44, 68, ISBN 978-0-691-15498-5.