Граф рыцарей - Knights graph

Граф рыцаря
${\displaystyle 8\times 8}$ граф рыцаря
Вершины	${\displaystyle mn}$
Края	${\displaystyle 4mn-6(m+n)+8}$ (если ${\displaystyle n\geq 2}$ и ${\displaystyle m\geq 2}$)
Обхват	4 (если ${\displaystyle n\geq 3}$ и ${\displaystyle m\geq 5}$)
Характеристики	двудольный
Таблица графиков и параметров

В теория графов, а граф рыцаря, или график рыцарского тура, это график который представляет все законные действия рыцарь шахматы кусок на шахматная доска. Каждый вершина на этом графике представляет собой квадрат шахматной доски, и каждое ребро соединяет два квадрата, которые являются ходом коня отдельно друг от друга. ${\displaystyle m\times n}$ граф рыцаря - граф рыцаря ${\displaystyle m\times n}$ шахматная доска.^[1]Его вершины можно представить как точки Евклидова плоскость чей Декартовы координаты ${\displaystyle (x,y)}$ целые числа с ${\displaystyle 1\leq x\leq m}$ и ${\displaystyle 1\leq y\leq n}$ (точки в центрах квадратов шахматной доски) и с двумя вершинами, соединенными ребром, когда их Евклидово расстояние является ${\displaystyle {\sqrt {5}}}$.

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

А Гамильтонов цикл на графе коня есть (замкнутая) рыцарский тур.^[1] Шахматная доска с нечетным числом клеток не имеет обхода, потому что граф коня - это двудольный граф и только двудольные графы с четным числом вершин могут иметь гамильтоновы циклы. На всех досках с четным числом клеток, кроме конечного, идет конь; Теорема Швенка предоставляет точный список того, какие из них работают, а какие нет.^[3]

Когда он изменен, чтобы иметь тороидальные граничные условия (это означает, что конь не блокируется краем доски, а вместо этого переходит на противоположный край) ${\displaystyle 4\times 4}$ граф рыцаря такой же, как и четырехмерный граф гиперкуба.^[3]

Смотрите также

• Граф короля
• График ладьи

Рекомендации

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

внешняя ссылка

• Вайсштейн, Эрик В. «Граф рыцаря». MathWorld.