Граф короля

График ходов короля на шахматной доске

В теории графов граф короля — это граф , который представляет все допустимые ходы шахматной фигуры короля на шахматной доске , где каждая вершина представляет собой клетку на шахматной доске, а каждое ребро — допустимый ход. Более конкретно, граф короля — это граф короля шахматной доски. ^[1] Это граф карты, образованный из клеток шахматной доски путем создания вершины для каждой клетки и ребра для каждых двух клеток, которые имеют общую ребро или угол. Его также можно построить как сильное произведение двух графов путей . ^[2] ${\displaystyle n\times m}$ ${\displaystyle n\times m}$

Для графа короля общее число вершин равно , а число ребер равно . Для графа квадратного короля это упрощается так, что общее число вершин равно , а общее число ребер равно . ^[3] ${\displaystyle n\times m}$ ${\displaystyle nm}$ ${\displaystyle 4nm-3(n+m)+2}$ ${\displaystyle n\times n}$ ${\displaystyle n^{2}}$ ${\displaystyle (2n-2)(2n-1)}$

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

В рисунке графа короля, полученного из шахматной доски, есть пересечения, но можно получить рисунок с меньшим количеством пересечений , соединив двух ближайших соседей каждой угловой клетки кривой вне шахматной доски вместо диагонального отрезка. Таким образом, пересечения всегда возможны. Для графа короля маленьких шахматных досок другие рисунки приводят к еще меньшему количеству пересечений; в частности, каждый граф короля является планарным графом . Однако, когда оба и не менее четырех, и они оба не равны четырем, — это оптимальное количество пересечений. ^{[6] [7]} ${\displaystyle n\times m}$ ${\displaystyle (n-1)(m-1)}$ ${\displaystyle (n-1)(m-1)-4}$ ${\displaystyle 2\times n}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle (n-1)(m-1)-4}$

Смотрите также

• Граф Рыцаря
• Граф королевы
• Граф Рукса
• График Бишопа
• Решётчатый граф
• Шахматный портал

Ссылки

1. Чанг, Джерард Дж. (1998), «Алгоритмические аспекты доминирования в графах», в Ду, Дин-Чжу; Пардалос, Панос М. (ред.), Справочник по комбинаторной оптимизации, т. 3 , Бостон, Массачусетс: Kluwer Acad. Publ., стр. 339–405, MR  1665419. Чанг определяет граф короля на стр. 341.
2. Беренд, Дэниел; Корах, Эфраим; Цукер, Шира (2005), «Двухцветная антираскраска планарных и родственных графов» (PDF) , 2005 Международная конференция по анализу алгоритмов , Труды по дискретной математике и теоретической информатике, Нэнси: Ассоциация по дискретной математике и теоретической информатике, стр. 335–341, MR  2193130.
3. Sloane, N. J. A. (ред.). "Последовательность A002943". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
4. Смит, Элви Рэй (1971), «Двумерные формальные языки и распознавание образов клеточными автоматами», 12-й ежегодный симпозиум по теории коммутации и автоматов , стр. 144–152, doi :10.1109/SWAT.1971.29.
5. Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), «Проблемы центра и диаметра в плоских триангуляциях и квадрангулях», Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '02), стр. 346–355, CiteSeerX 10.1.1.1.7694 , ISBN  0-89871-513-X.
6. Клещ, Мариан; Петриллова, Яна; Вало, Матуш (2013), «Минимальное количество пересечений в сильном произведении путей», Карпатский математический журнал , 29 (1): 27–32, doi : 10.37193/CJM.2013.01.13 , JSTOR  43999517, MR  3099062
7. Ма, Дэнджу (2017), «Число пересечений сильного произведения двух путей» (PDF) , The Australasian Journal of Combinatorics , 68 : 35–47, MR  3631655