キングのグラフ

キングのグラフ
${\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}$
グラフとパラメータの表

グラフ理論において、キンググラフとは、チェス盤上のキングの駒の有効な動きをすべて表すグラフであり、各頂点はチェス盤上のマス目を表し、各辺は有効な動きを表す。より具体的には、キンググラフはチェス盤のキンググラフである。^{[ 1 ]}キンググラフは、チェス盤のマス目から、各マス目を頂点とし、辺または角を共有する2つのマス目を辺として形成されるマップグラフである。また、 2つのパスグラフの強積として構築することもできる。^{[ 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 ]} キンググラフの一般化はキンググラフと呼ばれ、スクエアグラフ（各境界面が四辺形で各内部頂点に少なくとも4つの隣接頂点がある平面グラフ）から、スクエアグラフの各四辺形面の2つの対角線を追加することによって形成される。^{[ 5 ]}

チェス盤から得られるキンググラフの描画には交差が存在するが、各コーナーマスの2つの最近傍マスを対角線ではなくチェス盤の外側の曲線で結ぶことで、交差の少ない描画を実現できる。このようにすれば、交差は常に起こり得る。小さなチェス盤のキンググラフの場合、他の描画方法を用いると交差はさらに少なくなる。特に、すべてのキンググラフは平面グラフである。しかし、とが両方とも4以上で、かつ両方が4ではない場合、交差の最適な数はとなる。^{[ 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. Chang, Gerard J. (1998), 「グラフにおける支配のアルゴリズム的側面」, Du, Ding-Zhu; Pardalos, Panos M. (編), Handbook of combinatorial optimization, Vol. 3 , Boston, MA: Kluwer Acad. Publ., pp.  339– 405, MR  1665419チャンは341ページでキンググラフを定義しています。
2. Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005)、「平面グラフと関連グラフの2色逆色付け」(PDF)、2005 International Conference on Analysis of Algorithms、Discrete Mathematics & Theoretical Computer Science Proceedings、ナンシー: Association for Discrete Mathematics & Theoretical Computer Science、pp.  335– 341、MR 2193130 。
3. Sloane, N. J. A. (編). 「シーケンスA002943」 .整数シーケンスのオンライン百科事典. OEIS財団.
4. スミス、アルヴィ・レイ（1971）、「2次元形式言語とセルラーオートマトンによるパターン認識」、スイッチングとオートマトン理論に関する第12回年次シンポジウム、pp.  144– 152、doi：10.1109/SWAT.1971.29。
5. Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002)、「平面三角形分割と四角形分割における中心と直径の問題」、第13回ACM-SIAM離散アルゴリズムシンポジウム（SODA '02）の議事録、pp.  346–355、CiteSeerX 10.1.1.1.7694、ISBN  0-89871-513-X。
6. クレシュチ、マリアン;ペトリロバ、ヤナ。 Valo, Matúš (2013)、「パスの強い積における交差の最小数」、Carpathian Journal of Mathematics、29 (1): 27–32、doi : 10.37193/CJM.2013.01.13、JSTOR 43999517、MR 3099062  
7. Ma, Dengju (2017)、「2つのパスの強積の交差数」(PDF)、The Australasian Journal of Combinatorics、68 : 35–47、MR 3631655