警官番号

数学の一分野であるグラフ理論において、無向グラフの警官数または警官番号とは、グラフ上の特定の追跡・逃走ゲームで確実に勝利する（つまり、強盗を捕らえる）のに十分な警官の最小の数である。

このゲームでは、1人のプレイヤーが一定数の警官の位置をコントロールし、もう1人のプレイヤーが強盗の位置をコントロールします。警官は同じ位置に移動して強盗を捕まえようとしますが、強盗は捕まらないように努めます。したがって、プレイヤーは順番に次のアクションを実行します。^[1]

• ゲームの最初のターンでは、警官を操作するプレイヤーは各警官をグラフの頂点に配置します (同じ頂点に複数の警官を配置することもできます)。
• 次に、強盗を操作するプレイヤーは、強盗をグラフの頂点に配置します。
• 以降の各ターンでは、警官を操作しているプレイヤーは警官のサブセット (空の場合もある) を選択し、これらの警官をそれぞれ隣接する頂点に移動します。残りの警官 (いる場合) はそのまま残ります。
• 強盗の番では、強盗は隣接する頂点に移動するか、その場に留まるかを選択できます。

強盗が警官と同じ頂点を占めると、ゲームは警官の勝利で終了します。これが起こらない場合は、強盗が勝ちます。

グラフの警官数とは、警官がゲームに勝つことができる最小の数である。[ ^1]${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$${\displaystyle G}$

ツリー上では、警官の数は 1 です。警官はどこからでも開始でき、各ステップで強盗に近い唯一の隣人に移動します。警官の各ステップは、強盗が閉じ込められているサブツリーのサイズを縮小するため、最終的にゲームは終了します。

長さが 3 を超えるサイクル グラフでは、警官の数は 2 です。警官が 1 人だけの場合、強盗は警官から 2 歩離れた位置に移動し、強盗が移動するたびに常に同じ距離を維持できます。このようにして、強盗は捕まるのを永遠に回避できます。ただし、警官が 2 人いる場合は、1 人が 1 つの頂点に留まり、強盗ともう 1 人の警官が残りのパスでプレイするようにすることができます。もう 1 人の警官がツリー戦略に従うと、強盗は最終的に負けます。

内周が4より大きいグラフはすべて、その最小次数以上のコップ数を持ちます。^[2]したがって、コップ数が任意に高いグラフが存在することになります。

数学における未解決の問題:

-頂点グラフの最大 cop 数はいくつですか?${\displaystyle n}$

（数学における未解決の問題がさらに増える）

アンリ・メイニエル（メイニエルグラフでも知られる）は1985年に、連結された-頂点グラフはすべてコップ数 を​​持つと予想した。有限射影平面のレヴィグラフ（または接続グラフ）は内周が6で最小次数が であるため、これが真実であればこの境界は最良のものとなる。^[3]${\displaystyle n}$${\displaystyle O({\sqrt {n}})}$${\displaystyle \Omega ({\sqrt {n}})}$

すべてのグラフには、準線形の警官数がある。これを証明する 1 つの方法は、1 台の警官で守れるサブグラフを使用することである。警官は、強盗を追跡するために移動することができ、強盗がサブグラフに移動した場合、警官は強盗を即座に捕まえることができる。守れるサブグラフには、 1 つの頂点の閉近傍と、任意の 2 つの頂点間の最短経路の 2 種類がある。次数直径問題におけるムーアの境界は、これら 2 種類の守れる集合の少なくとも 1 つがサイズ であることを意味する。1 台の警官を使ってこの集合を守り、グラフの残りの頂点の接続成分内を再帰的に調べると、警官数は最大 であることがわかる。^{[3] [4]}${\displaystyle \Omega (\log n/\log \log n)}$${\displaystyle O(n\log \log n/\log n)}$

警官数に対するより強い準線形上限、

${\displaystyle {\frac {n}{2^{(1-o(1)){\sqrt {\log n}}}}},}$

は知られている。しかし、厳密な境界を得る問題とメイニエルの予想を証明または反証する問題は未解決のままである。コップ数が常にである定数が存在するというソフトメイニエル予想が正しいかどうかさえわかっていない。^[3]${\displaystyle c<1}$${\displaystyle O(n^{c})}$

与えられたグラフのcop数を計算することはEXPTIME困難であり^[5]、パラメータ化された複雑さに対しては困難である^[6]。

警官勝利グラフは警官数が1であるグラフである。^[1]

すべての平面グラフのコップ数は最大で3です。^[1] より一般的には、すべてのグラフのコップ数は最大でその種数に比例します。^[7]しかし、種数に関するコップ数の最もよく知られている下限は、おおよそ種の平方根であり、種数が大きい場合、上限から大きく離れます。^[2]

グラフのツリー幅は追跡回避ゲームの結果としても得られますが、このゲームでは、強盗は各ターンで単一のエッジではなく任意の長さのパスに沿って移動できます。この余分な自由度は、警官の数が一般にツリー幅よりも小さいことを意味します。より具体的には、ツリー幅 のグラフでは、警官の数は最大で です。^[8]${\displaystyle w}$${\displaystyle \lfloor w/2\rfloor +1}$