график Кинга

график Кинга
график Кинга
	королевский график
Вершины
Края
Обхват	когда
Хроматическое число	когда
Хроматический индекс	когда
	Таблица графиков и параметров

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

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

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

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

См. также

Ссылки

^ Чанг, Джерард Дж. (1998), «Алгоритмические аспекты доминирования на графиках», в Du, Ding-Zhu; Pardalos, Panos M. (Eds.), Справочник по комбинаторной оптимизации, Vol. 3 , Бостон, Массачусетс: Kluwer Acad. Publ., Pp. 339–405, MR 1665419 . Чанг определяет график короля на с. 341 .
^ Беренд, Даниэль; Корач, Эфраим; Zucker, Shira (2005), «Двухнологические планарные и связанные с ними графики» (PDF) , 2005 Международная конференция по анализу алгоритмов , дискретной математике и теоретических разбирательствах по информатике, Нэнси: Ассоциация по дискретной математике и теоретической информатике, стр. 335–341, MR 2193130 .
^ Слоан, Нью-Джерси (ред.). «Последовательность A002943» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
^ Смит, Элви Рэй (1971), «Двумерные формальные языки и распознавание образов клеточными автоматами», 12-й ежегодный симпозиум по теории коммутации и автоматов , стр. 144–152, doi : 10.1109/SWAT.1971.29 .
^ Чепой, Виктор; Драган, Федор; Ваксес, Янн (2002), «Проблемы центра и диаметра в плоских триангуляциях и четырехугольниках», Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '02) , стр. 346–355 , CiteSeerX 10.1.1.1.7694 , ISBN 0-89871-513-Х .
^ Клещ, Мариан; Петриллова, Яна; Вало, Матуш (2013), «Минимальное количество пересечений в сильном произведении путей», Карпатский математический журнал , 29 (1): 27–32, doi : 10.37193/CJM.2013.01.13 , JSTOR 43999517 , MR 9063
^ Ма, Денджу (2017), «Число пересечения сильного произведения двух путей» (PDF) , Австралазийский журнал комбинаторики , 68 : 35–47, MR 3631655

[1] Чанг, Джерард Дж. (1998), «Алгоритмические аспекты доминирования на графиках», в Du, Ding-Zhu; Pardalos, Panos M. (Eds.), Справочник по комбинаторной оптимизации, Vol. 3 , Бостон, Массачусетс: Kluwer Acad. Publ., Pp. 339–405, MR 1665419 . Чанг определяет график короля на с. 341 .

[2] Беренд, Даниэль; Корач, Эфраим; Zucker, Shira (2005), «Двухнологические планарные и связанные с ними графики» (PDF) , 2005 Международная конференция по анализу алгоритмов , дискретной математике и теоретических разбирательствах по информатике, Нэнси: Ассоциация по дискретной математике и теоретической информатике, стр. 335–341, MR 2193130 .

[3] Слоан, Нью-Джерси (ред.). «Последовательность A002943» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[4] Смит, Элви Рэй (1971), «Двумерные формальные языки и распознавание образов клеточными автоматами», 12-й ежегодный симпозиум по теории коммутации и автоматов , стр. 144–152, doi : 10.1109/SWAT.1971.29 .

[5] Чепой, Виктор; Драган, Федор; Ваксес, Янн (2002), «Проблемы центра и диаметра в плоских триангуляциях и четырехугольниках», Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '02) , стр. 346–355 , CiteSeerX 10.1.1.1.7694 , ISBN 0-89871-513-Х .

[6] Клещ, Мариан; Петриллова, Яна; Вало, Матуш (2013), «Минимальное количество пересечений в сильном произведении путей», Карпатский математический журнал , 29 (1): 27–32, doi : 10.37193/CJM.2013.01.13 , JSTOR 43999517 , MR 9063

[7] Ма, Денджу (2017), «Число пересечения сильного произведения двух путей» (PDF) , Австралазийский журнал комбинаторики , 68 : 35–47, MR 3631655

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]