В теории графов графом ходов короля называется граф, изображающий все возможные ходы короля на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам. Чанг определяет граф ходов короля на стр. 341 .
Для графа ходов короля на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется .
Окрестность вершины в графе ходов короля соответствует окрестности Мура клеточного автомата. Обобщение графа ходов короля можно получить из рамочного графа (плоского графа, у которого каждая грань является четырёхугольником и каждая внутренняя вершина имеет по меньшей мере четыре соседа) путём добавления двух диагоналей для каждой четырёхугольной грани.
См. также Граф ходов коня Граф решётки Ладейный граф
Примечания
Категория:Параметрические семейства графов