WikiDer > Граф рыцарей - Википедия

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

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

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

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

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

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

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

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

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

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