Граф королей - Kings graph - Wikipedia

Граф короля
${\displaystyle 8\times 8}$ граф короля
Вершины	${\displaystyle nm}$
Края	${\displaystyle 4nm-3(n+m)+2}$
Обхват	${\displaystyle 3}$ когда ${\displaystyle \min(m,n)>1}$
Хроматическое число	${\displaystyle 4}$ когда ${\displaystyle \min(m,n)>1}$
Хроматический индекс	${\displaystyle 8}$ когда ${\displaystyle \min(m,n)>2}$
Таблица графиков и параметров

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

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

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

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

• Граф рыцаря
• График ладьи
• Решетчатый граф

Рекомендации

1. Чанг, Джерард Дж. (1998), «Алгоритмические аспекты доминирования в графах», в Du, Ding-Zhu; Пардалос, Панос М. (ред.), Справочник по комбинаторной оптимизации, Вып. 3, Бостон, Массачусетс: Kluwer Acad. Publ., Pp. 339–405, МИСТЕР  1665419. Чанг определяет граф короля на п. 341.
2. Беренд, Дэниел; Корах, Ефрем; Цукер, Шира (2005), «Двукрашивание плоских и родственных графов» (PDF), 2005 Международная конференция по анализу алгоритмов, Дискретная математика и теоретические материалы по информатике, Нэнси: Ассоциация дискретной математики и теоретической информатики, стр. 335–341, МИСТЕР  2193130.
3. Слоан, Н. Дж. А. (ред.). «Последовательность A002943». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
4. Смит, Элви Рэй (1971), «Двумерные формальные языки и распознавание образов клеточными автоматами», 12-й ежегодный симпозиум по теории коммутации и автоматов, стр. 144–152, Дои:10.1109 / SWAT.1971.29.
5. Чепой, Виктор; Драган, Федор; Ваксес, Янн (2002), "Проблемы центра и диаметра в плоских триангуляциях и четырехугольниках", Материалы тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '02), стр.346–355, CiteSeerX  10.1.1.1.7694, ISBN  0-89871-513-X.