Граф короля

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

В теории графов, А граф короля является график, который представляет все законные ходы короля шахмат кусок на шахматной доске, где каждая вершина представляет собой квадрат на шахматной доске, а каждое ребро является законным шагом. В частности, граф короля - это граф короля шахматной доски. Это граф карты, сформированный из квадратов шахматной доски путем создания вершины для каждого квадрата и ребра для каждых двух квадратов, имеющих общее ребро или угол. Его также можно построить как сильное произведение двух графов путей. ${\ Displaystyle п \ раз м}$${\ Displaystyle п \ раз м}$

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

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

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