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

В теории графов графом ходов короля называется граф, изображающий все возможные ходы короля на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам^[1].

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

Окрестность вершины в графе ходов короля соответствует окрестности Мура клеточного автомата^[2]. Обобщение графа ходов короля можно получить из рамочного графа (плоского графа, у которого каждая грань является четырёхугольником и каждая внутренняя вершина имеет по меньшей мере четыре соседа) путём добавления двух диагоналей для каждой четырёхугольной грани^[3].