クイーンのグラフ

クイーンのグラフ
a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h クイーングラフでは、上のチェス盤の各マスが頂点です。クイーンが移動できる2つの頂点間には辺が存在します。例えば、 d4に隣接する頂点には白い点が示されています（つまり、d4から各点に辺が存在します）。${\displaystyle 8\times 8}$
頂点	${\displaystyle mn}$
彩色数	nの場合${\displaystyle m=n\equiv 1,5{\pmod {6}}}$
性質	双連結、ハミルトン
グラフとパラメータの表

数学において、クイーングラフとは、チェス盤におけるクイーン（チェスの駒）の有効な動きを表す無向グラフです。グラフの各頂点はチェス盤上のマス目を表し、各辺はクイーンが行える有効な動き、つまり任意の数のマス目による水平、垂直、または斜めの動きを表します。チェス盤の次元が である場合、誘導グラフはクイーングラフと呼ばれます。 ${\displaystyle m\times n}$ ${\displaystyle m\times n}$

グラフの独立セットは、 2つのクイーンが互いに攻撃し合っていない複数のクイーンの配置に対応します。これらは、標準的なチェス盤上に攻撃しない8つのクイーンを配置する「エイトクイーンパズル」で研究されます。支配セットは、すべてのマスがクイーンによって攻撃または占有されているクイーンの配置を表します。5つのクイーン以上でチェス盤を支配することができます。 ${\displaystyle 8\times 8}$ ${\displaystyle 8\times 8}$

グラフの色分けは、クイーンが同じ色の 2 つのマス目の間で移動できないように各マス目を色分けする方法を表しています。チェス盤には少なくともn色が必要ですが、ボードには 9 色が必要です。 ${\displaystyle n\times n}$ ${\displaystyle 8\times 8}$

性質

各クイーングラフにはハミルトン閉路が存在し、グラフは双連結である（どの頂点を一つ削除しても連結されたままである）。およびクイーングラフの特別なケースは完全である。^[1]${\displaystyle 1\times n}$ ${\displaystyle 2\times 2}$

独立性

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

チェス盤上の8個の独立集合（このような集合は必然的に支配的でもある）。^[2]${\displaystyle 8\times 8}$

グラフの独立集合は、チェス盤上で複数のクイーンが互いに攻撃し合わない配置に対応する。チェス盤では、同じ行または列に2つのクイーンが存在できないため、最大の独立集合は最大でn個の頂点を含む。 ^{[2]この上限は、} n = 2とn = 3を除くすべてのnに対して達成できる。^[3] n = 8の場合、これは伝統的な8クイーンパズルである。^[2]${\displaystyle n\times n}$

支配

クイーングラフの支配集合は、チェス盤上のすべてのマスがクイーンによって攻撃されるか占有されるようなクイーンの配置に対応します。チェス盤では5つのクイーンが支配することができ、これは可能な最小数です^{[4] ：113～114}（4つのクイーンは少なくとも2つのマスを攻撃されないままにします）。5つのクイーンのこのような配置は4,860通りあり、その中にはクイーンが占有されているすべてのマスも支配するもの、つまりそれぞれが攻撃し、互いに守り合うものも含まれます。このサブグループには、クイーンが主対角線上のマスのみを占める位置^{[4] ：113～114}（例：a1からh8）、またはすべての副対角線上（例：a2からg8）を占める位置もあります^{[5] [6]}${\displaystyle 8\times 8}$

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h 4

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h 3

a b c d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b c d e f g h 2

1${\displaystyle 8\times 8}$

サイズ5の支配的な（そして独立した）セット

主対角線上の支配的なセット。${\displaystyle 3\times 3}$ ${\displaystyle 5\times 5}$ ${\displaystyle 5\times 5}$

下対角線上の支配的なセット。

ループのない長方形のチェス盤をトーラスまたは円筒に置き換えてグラフを修正すると、最小支配集合のサイズは4に減少します。[4] : 139${\displaystyle n\times n}$ ${\displaystyle d(n)\leq dd(n)}$ ${\displaystyle d(8)=dd(8)=5}$ ${\displaystyle d(11)=5,dd(11)=7}$

点線のマスは中央のマスに隣接しています。隣接していない8つのマスは、対応するナイトグラフにおいて隣接しています。^{[4] : 117}

${\displaystyle {\frac {n-1}{2}}\leq d(n)\leq n-\left\lfloor {\frac {n}{3}}\right\rfloor .}$

のd ( n )の初期値は、1、1、1、2、3、3、4、5、5、5、5( OEISのシーケンスA075458 )です。 ${\displaystyle n=1,2,3,\dots }$

K _{n を、}すべての数が同一の偶奇性を持ち、どの3つの数も等差数列を形成しないようなの部分集合の最大の大きさとする（この集合は「中点フリー」である）。クイーングラフの対角支配数はである。^{[4] : 116}${\displaystyle \{1,2,3,\dots ,n\}}$ ${\displaystyle n\times n}$ ${\displaystyle n-K_{n}}$

独立支配数ID ( n )を、クイーングラフにおける最小の独立支配集合の大きさと定義する。^[7]${\displaystyle n\times n}$ ${\displaystyle ID(n)<0.705n+0.895}$

色分け

クイーングラフの9色分け。 ^[8]同じ色のマス目は、同じ列、列、または対角線上にないため、クイーンはマス目間を直接移動できないことに注意してください${\displaystyle 8\times 8}$

クイーングラフの彩色とは、隣接する2つの頂点が同じ色にならないように各頂点に色を割り当てることです。例えば、a8を赤に塗った場合、クイーンはa8からこれらのマス目のいずれかに移動できるため、a列、8段、または長対角線上の他のマス目を赤に塗ることはできません。グラフの彩色数は、グラフを彩色するために使用できる最小の色数です。

クイーングラフの場合、各マス目は異なる色で表示されるため（つまり、行と列はクリークであるため） 、少なくともn色が必要です。 ^[1]彩色数は、（つまり、nが6の倍数より1つ多いか1つ少ない場合） nとなります。 ^[9]${\displaystyle n\times n}$ ${\displaystyle n\equiv 1,5{\pmod {6}}}$

クイーングラフの彩色数は9である。 ^[10]${\displaystyle 8\times 8}$

非冗長性

頂点の集合が非冗長であるとは、集合から任意の頂点を削除すると集合の近傍が変化する、つまり各頂点に対して、集合内の他のどの頂点にも隣接しない隣接頂点が存在する場合を指します。これは、それぞれが少なくとも1つのマスを一意に制御するクイーンの集合に対応します。クイーングラフ上の非冗長集合の最大サイズIR ( n )を特徴付けることは困難であり、既知の値には^{[4] : 206–207 が含まれます}${\displaystyle n\times n}$ ${\displaystyle IR(5)=5,IR(6)=7,IR(7)=9,IR(8)=11.}$

追跡と逃走のゲーム

クイーングラフ上の追跡・回避ゲームを以下のルールに従ってプレイすることを考えてみよう。白のクイーンが片方の角からスタートし、黒のクイーンが反対側の角からスタートする。プレイヤーは交互に動き、クイーンを（水平、垂直、斜めのいずれの方向でも）通過せずに到達できる隣接頂点に移動するか、反対側のクイーンに隣接する頂点に着地するかのいずれかを行う。このゲームは、ペアリング戦略を用いる白が勝利できる。^[11]${\displaystyle 8\times 8}$

参照

• キンググラフ
• ナイトグラフ
• ルークグラフ
• ビショップグラフ
• チェスポータル

参考文献

1. Weisstein, Eric W. "Queen Graph" . MathWorld
2. アバーバッハ、ボニー、チェイン、オリン (2000).レクリエーション数学による問題解決.ドーバー出版. pp.  211– 212. ISBN 9780486131740。
3. Bernhardsson, Bo (1991). 「すべてのNに対するNクイーン問題の明示的解」. ACM SIGART Bulletin . 2 (2): 7. doi : 10.1145/122319.122322 . S2CID  10644706
4. ワトキンス、ジョン・J. (2012). 『アクロス・ザ・ボード：チェス盤問題の数学』プリンストン大学出版局.
5. 支配的な女王 - researchgate.net
6. チェス盤上の5つのクイーン
7. Cockayne, EJ (1990). 「チェス盤支配問題」.離散数学. 86 ( 1–3 ): 13–20 . doi : 10.1016/0012-365X(90)90344-H . hdl : 1828/2415 .
8. アイアー, MR; メノン, VV (1966). 「チェス盤の色付けについて」.アメリカ数学月刊誌. 72 (7): 723.${\displaystyle n\times n}$
9. Chvátal, Václav . 「Colouring the queen graphs」 . 2022年2月14日閲覧。
10. ベル、ジョーダン；スティーブンス、ブレット (2009). 「n-クイーンに関する既知の結果と研究分野の概観」離散数学. 309 (1): 1– 31. doi : 10.1016/j.disc.2007.12.043 .
11. Averbach & Chein 2000、257–258、443。