國王的圖

國王的圖
國王的圖
頂點
邊緣
周長 什麼時候
色數 什麼時候
色度指數 什麼時候
圖和參數表

在圖理論中，國王的圖是一個圖形，代表國王國際象棋棋盤上的所有法律移動，每個頂點代表棋盤上的正方形，每個邊緣都是法律上的舉動。更具體地說，一個國王的圖是國王的圖棋盤。它是通過為每個正方形的頂點製作一個頂點的棋盤正方形的地圖圖，而每個正方形的邊緣則是一個具有邊緣或角落的正方形。它也可以作為兩個路徑圖的強產物構造。

為國王的圖總數是邊的數量是 。對於一個正方形國王的圖簡化了，以使頂點總數為邊緣總數是 。

國王圖中的頂點的鄰域對應於Moore鄰居的蜂窩自動機。國王圖的概括稱為kinggraph ，由方形圖（平面圖）形成（每個有界的臉是四邊形的，每個內部頂點至少具有四個鄰居），通過添加每個四邊形的兩個對角線。 。

在從一個從一個國王圖的圖中獲得棋盤，有穿越，但是可以通過將每個角正方形的兩個最近的鄰居通過棋盤外面的曲線而不是通過對角線線段連接到每個角正方形的兩個鄰居來獲得更少的橫梁。這樣， 穿越總是可能的。對於國王的小棋盤圖，其他圖紙的穿越甚至更少。特別是每個國王的圖是平面圖。但是，當兩者都和至少四個，它們都不等於四個， 是最佳的交叉數。

也可以看看