Граф ходів короля

У теорії графів граф ходів короля — граф, що зображує всі можливі ходи короля на шахівниці; кожна вершина відповідає клітинці на дошці, а ребра відповідають можливим ходам.

Граф ходів короля
Граф ходів короля 8 × 8
(Вершин)	nm
(Ребер)	4nm - 3(n + m) + 2
(Обхват)	${\displaystyle 3}$ якщо ${\displaystyle \min(m,n)>1}$
Хроматичне число	${\displaystyle 4}$ when ${\displaystyle \min(m,n)>1}$
Хроматичний індекс	${\displaystyle 8}$ when ${\displaystyle \min(m,n)>2}$

Для графа ходів короля на дошці розміру ${\displaystyle n\times m}$ число вершин дорівнює ${\displaystyle nm}$. Для дошки ${\displaystyle n\times n}$ число вершин дорівнює ${\displaystyle n^{2}}$, а число ребер дорівнює ${\displaystyle (2n-2)(2n-1)}$.

Окіл вершини в графі ходів короля відповідає околу Мура клітинного автомата. Узагальнення графа ходів короля можна отримати з рамкового графа (плоского графа, в якого кожна грань є чотирикутником і кожна внутрішня вершина має принаймні чотири сусіди), додавши для кожної чотирикутної грані дві діагоналі.

Див. також

• Граф ходів коня
• Граф решітки
• Туровий граф

•  

Примітки

1. Alvy Ray Smith. 12th Annual Symposium on Switching and Automata Theory. — 1971. — С. 144–152. — DOI:10.1109/SWAT.1971.29.
2. Victor Chepoi, Feodor Dragan, Yann Vaxès. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02). — 2002. — 30 червня. — С. 346–355.