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

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

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

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

Див. також

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

• Шаблон:Portal-inline