У теорії графів граф ходів короля — граф, що зображує всі можливі ходи короля на шахівниці; кожна вершина відповідає клітинці на дошці, а ребра відповідають можливим ходам.
Для графа ходів короля на дошці розміру число вершин дорівнює . Для дошки число вершин дорівнює , а число ребер дорівнює .
Окіл вершини в графі ходів короля відповідає околу Мура клітинного автомата. Узагальнення графа ходів короля можна отримати з рамкового графа (плоского графа, в якого кожна грань є чотирикутником і кожна внутрішня вершина має принаймні чотири сусіди), додавши для кожної чотирикутної грані дві діагоналі.
Див. також
Граф ходів коня Граф решітки Туровий граф
Примітки