Граф ходов короля
| Граф ходов короля | |
|---|---|
 Граф ходов короля 8 × 8 | |
| Вершин | nm |
| Рёбер | 4nm - 3(n + m) + 2 |
В теории графов графом ходов короля называется граф, изображающий все возможные ходы короля на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам[1].
Для графа ходов короля на доске размера [math]\displaystyle{ n \times m }[/math] число вершин равняется [math]\displaystyle{ n m }[/math]. Для доски [math]\displaystyle{ n \times n }[/math] число вершин равняется [math]\displaystyle{ n^2 }[/math], а число рёбер равняется [math]\displaystyle{ (2n-2)(2n-1) }[/math].
Окрестность вершины в графе ходов короля соответствует окрестности Мура клеточного автомата[2]. Обобщение графа ходов короля можно получить из рамочного графа (плоского графа, у которого каждая грань является четырёхугольником и каждая внутренняя вершина имеет по меньшей мере четыре соседа) путём добавления двух диагоналей для каждой четырёхугольной грани[3].
См. также
Примечания
- ↑ Gerard J. Chang. Handbook of combinatorial optimization, Vol. 3 / Ding-Zhu Du, Panos M. Pardalos. — Boston, MA: Kluwer Acad. Publ., 1998. — С. 339–405.. Чанг определяет граф ходов короля на стр. 341 Архивная копия от 24 апреля 2017 на Wayback Machine
- ↑ Alvy Ray Smith. 12th Annual Symposium on Switching and Automata Theory. — 1971. — С. 144–152. — doi:10.1109/SWAT.1971.29.
- ↑ Victor Chepoi, Feodor Dragan, Yann Vaxès. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02). — 2002. — С. 346–355.