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

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

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

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

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

Див. також

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

•   Портал «Шахи»