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

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

Граф ходов короля
Граф ходов короля 8 × 8
Вершин	nm
Рёбер	4nm - 3(n + m) + 2

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

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

См. такжеПравить

• Граф ходов коня
• Граф решётки
• Ладейный граф