ビショップグラフ

数学において、ビショップグラフとは、チェス盤上のチェスの駒（ビショップ）の全ての有効な動きを表すグラフです。各頂点はチェス盤上のマス目を表し、各辺はビショップの有効な動きを表します。つまり、2つの頂点（マス目）が共通の対角線を占める場合、それらの頂点（マス目）の間には辺が存在します。チェス盤の次元が である場合、誘導グラフはビショップグラフと呼ばれます。 ${\displaystyle m\times n}$ ${\displaystyle m\times n}$

プロパティ

チェス盤には赤と黒の2色のマス目があり、水平または垂直に隣接するマス目は反対色であるという事実は、ビショップグラフが2つの連結成分を持ち、その頂点集合がそれぞれ赤と黒のマス目であることを意味する。これは、ビショップの対角線上の移動では色を変えることができないが、1回以上の移動で、ビショップは任意のマス目から同じ色の任意のマス目に移動できるためである。^{[ 1 ]} 2つの成分は、盤の片側の長さが偶数の場合同型であるが、両側が奇数の場合は同型ではない。

ビショップグラフの要素は、元の盤が正方形で辺の長さが奇数の場合、ダイヤモンド上のルークグラフとして扱うことができます。なぜなら、赤い正方形（例えば）を45度回転させると、ビショップの動きがルークの動きと同じように水平と垂直になるからです。^{[ 2 ]}

支配

ビショップが 1 手でそのマスに到達できる場合、そのマスはビショップによって攻撃されていると言われます。支配集合とは、すべてのマスがいずれかのビショップによって攻撃または占有されるようなビショップの配置です。独立支配集合とは、ビショップが他のビショップを攻撃しない支配集合です。n 辺の正方形のボードを支配するために必要なビショップの最小数はちょうど n であり、これは独立支配集合を形成できるビショップの最小数でもあります。対照的に、ビショップによって占有されているマスも含めすべてのマスがいずれかのビショップによって攻撃される支配集合である完全支配集合は、より多くのビショップを必要とします。n ≥ 3 の正方形のボードでは、完全支配集合の最小サイズは最小支配集合の約 1/3 大きくなります。^{[ 3 ] [ 4 ]}${\displaystyle 2\lceil 2(n-1)/3\rceil ,}$

参考文献

1. Berghammer, Rudolf (2012). 「関係代数モデリングとチェス盤の独立性問題および支配問題の解法」 . The Journal of Logic and Algebraic Programming . 81 (6): 625– 642. doi : 10.1016/J.JLAP.2012.05.001 .
2. Hedetniemi, Jason T.; Hedetniemi, Stephen T. (2020年9月). 「チェス盤における支配」. Haynes, Teresa W.; Hedetniemi, Stephen T.; Henning, Michael A. (編).グラフにおける支配構造. 数学の発展. 第66巻. Springer International Publishing. pp.  341– 386. doi : 10.1007/978-3-030-58892-2_12 . ISBN 9783030588922。
3. Cockayne, EJ; Gamble, B.; Shepherd, B. (1986). 「ビショップグラフの支配パラメータ」 .離散数学. 58 (3): 221– 227. doi : 10.1016/0012-365X(86)90139-1 .
4. Cockayne, EJ (1990). 「チェス盤支配問題」.離散数学. 86 ( 1–3 ): 13–20 . doi : 10.1016/0012-365X(90)90344-H . hdl : 1828/2415 .