警官勝利グラフ
Type of graph related to pursuit–evasion

グラフ理論 では、cop-win グラフは、追跡者 (警官) が強盗との追跡・回避ゲームで必ず勝てる無向グラフであり、プレーヤーは交互にグラフのエッジに沿って移動するか、警官が強盗の頂点に止まるまでその場に留まるかを選択できます。[1]有限 cop-win グラフは、支配頂点 (その閉近傍が別の頂点の近傍のサブセットである頂点)を繰り返し削除することで解体したり、そのような頂点を繰り返し追加することで構築したりできるため、解体可能グラフまたは構成可能グラフとも呼ばれます。cop-win グラフは、解体順序を構成する貪欲アルゴリズムによって多項式時間で認識できます。これらには、弦グラフやユニバーサル頂点を含むグラフが含まれます。

定義

追跡と逃亡

警官勝利グラフは、警官と強盗の2人のプレイヤーが与えられた無向グラフの異なる初期頂点に配置される追跡・回避ゲームによって定義できます。警官が最初に初期頂点を選択し、次に強盗が選択します。次に、彼らは交代でゲームをプレイしますが、やはり警官が最初になります。各プレイヤーのターンでは、プレイヤーは隣接する頂点に移動するか、その場に留まるかを選択できます。警官が強盗と同じ頂点でターンを終了できればゲームは終了し、警官の勝利となります。強盗は警官を無期限に回避することで勝利します。警官勝利グラフとは、プレイヤーが開始位置を選択し、このように移動することで、警官が常に勝利を強制できるという特性を持つグラフです。無向グラフが警官勝利グラフでない場合は、強盗勝利グラフと呼ばれます。[2]

解体

このグラフでは、頂点vは頂点wによって支配されています。つまり、 vの閉近傍、N [ v ] （内側の影付き領域）は、 wの閉近傍、N [ w ]（外側の影付き領域）のサブセットです。

与えられたグラフにおける頂点vの閉近傍 N [ v ]は、 v自身とvに隣接する他のすべての頂点からなる頂点の集合である。N [ v ] ⊂ N [ w ]が成り立つとき、頂点 v は別の頂点 w に支配されているという。つまり、 vとwは隣接しており、 vの他のすべての隣接頂点はwにも隣接している。[3] Nowakowski & Winkler (1983) は、別の頂点に支配されている頂点を既約頂点と呼んでいる。[2]

与えられたグラフの解体順序または支配除去順序とは、頂点をこの順序で一つずつ取り除いた場合、各頂点（最後の頂点を除く）は取り除かれた時点で支配されるような順序である。グラフが解体可能であるのは、解体順序を持つ場合のみである。[2] [3]

勝利と解体可能性の同等性

すべての有限分解可能グラフは警官勝ちである。これは、頂点が 1 つのグラフ（警官が自明に勝つ）を基本ケースとして、数学的帰納法によって証明できる。より大きなグラフの場合、 v を任意の支配頂点とする。帰納法の仮説によれば、警官はv を除去して形成されるグラフ上で勝利戦略を持ち、強盗が実際にvにいるときはいつでも、強盗がv を支配する頂点にいると仮定することによって、元のグラフで同じ戦略に従うことができる。この戦略に従うと、ゲームに実際に勝つか、強盗がvにいて警官が支配頂点にいる位置になり、警官があと 1 手で勝つことができる。[2] [4] n頂点のグラフでこの帰納的戦略に従う警官は、開始位置に関わらず、勝つのに最大でn手で済む。警官の開始位置を慎重に選択することで、同じ考え方を使って、n頂点グラフでは警官が最大でn −4手で勝利を強制できることを証明することができます。[5] [6] [7]

逆に、すべての警官勝利グラフには支配頂点がある。なぜなら、支配頂点のないグラフでは、強盗がまだ負けていない場合、警官に隣接しない位置への安全な動きがあり、強盗は各ターンでこれらの安全な動きの1つを実行することでゲームを無限に続けることができるからである。[2] [8]さらに、vが警官勝利グラフの支配頂点である場合、v を削除すると別の警官勝利グラフが生成されなければならない。そうでなければ、強盗はその部分グラフ内でプレイし、警官が実際にvにいるときはいつでも、警官がvを支配する頂点にいると偽り、決して捕まらない可能性があるからである。これらの2つの原理からの帰納的に、すべての有限の警官勝利グラフは分解可能であることが示される。[2] [9]

閉鎖特性

1つのbcdefグラムh
8
h8 黒キング
a1 白のキング
8
77
66
55
44
33
22
11
1つのbcdefグラムh
チェス盤上で、警官役の 2 人の王のうちの 1 人が、強盗役のもう 1 人の王に勝つことができるため、王のグラフは警官勝利グラフになります。

数学的対象の族は、族のメンバーを組み合わせると必ずその族の別のメンバーが生成される場合、一連の演算に関して閉じていると言われる。その意味で、cop-win グラフの族はグラフの強積に関して閉じている。強積の各頂点は、2 つの因子グラフのそれぞれの頂点のペアに対応する。警官は、2 つの cop-win グラフの強積で、まず、これらの 2 つの因子グラフのいずれかで勝つためにプレイし、最初の要素が強盗と同じペアに到達することにより、勝つことができる。次に、最初の要素が強盗と同じペアのままで、警官は 2 つの因子の 2 番目で勝つためにプレイすることができる。[2] [10]たとえば、 2 つのパス グラフの強積であるキング グラフは cop-win である。このグラフでは、頂点はチェス盤のマス目に対応しており、警官と強盗はどちらもチェスの王のように、水平、垂直、または斜めに隣接するマス目に移動します。警官の積に基づく戦略は、まず強盗と同じ列に移動し、次に強盗と同じ列に留まりながら、強盗の列に向かって移動することです。[11]

警官勝利グラフのすべての誘導サブグラフが警官勝利であるというのは正しくありません。しかし、ある特別な誘導サブグラフは警官勝利のままです。Nowakowski & Winkler (1983) は、グラフGの誘導サブグラフHの1 つへの後退を、 Gの頂点からHの頂点への写像で、 Hの各頂点をそれ自身に写像し、Gの隣接する頂点の各ペアを、互いに同じ頂点または H 内の隣接する頂点のペアに写像するものと定義しています。すると、警官勝利グラフの族は後退に関して閉じています。これは、警官が G 内のゲームをシミュレートすることで H で勝つことができるためです。 Gでの勝利戦略が警官をその場に留まらせるか、端点がHの同じ頂点に写像されている辺をたどることを要求するときはいつでも、警官はH内に留まります。そして、他のすべてのケースでは、コップはGの勝利エッジの後退下の像であるHのエッジに従います。[2]

認識アルゴリズム

グラフがcop-winであるかどうかを判定し、もしそうであれば、copがグラフ内で勝利できるような分解シーケンスを見つけるための様々な戦略が知られています。これらには、貪欲アルゴリズムや、頂点の共通近傍を数えることに基づくより複雑なアルゴリズムが含まれます。

貪欲アルゴリズム

解体順序は、支配頂点を繰り返し見つけて削除する単純な貪欲アルゴリズムによって見つけることができます。この処理は、グラフがcop-winである場合にのみ、グラフを1つの頂点に削減することで成功します。したがって、この手法は解体順序を見つけるアルゴリズムを提供するだけでなく、与えられたグラフがcop-winであるかどうかをテストするアルゴリズムも提供します。このアルゴリズムが削除する支配頂点を見つける方法の一つは、以下の手順を実行することです。

  • グラフ内のすべての三角形を見つけ、各辺が関与する三角形の数を数えます。
  • vの次数から 1 を引いた数の三角形に関与する辺の端点である頂点vを繰り返し見つけ、 vを削除し、 vと三角形を形成していた残りの各辺の辺ごとに三角形の数を減らします。

n頂点、m辺、縮退度 dのグラフでは、このプロセスはO ( dm )の時間で実行できます 。[12]

隣人を数える

スピンラッド（2004）による、より複雑な代替アルゴリズムでは、隣接する頂点の組（x、y）ごとに、不足（ deficit ）と呼ばれる数値を維持する。これは、 xの隣接頂点のうちyの隣接頂点ではない頂点の数を数える。他の頂点を削除した後、この数値が0になった場合、x はyに支配されており、削除してもよい。このアルゴリズムは、不足が小さい組（x、y）についてのみ、 実際の不足集合（xの隣接頂点のうちyの隣接頂点ではない頂点）を構築し、維持する。[13]

計算を高速化するために、スピンラッドのアルゴリズムは、log 2  n個の頂点からなる小さなブロック内の近傍を数えるサブルーチンを使用します。Bがアルゴリズムによってブロックとして選択された頂点の集合である場合、他の任意の頂点については、 Bにおけるその頂点の近傍集合は、log 2 nビットの2進数として表すことができます。これらの数値により、アルゴリズムは任意の2つの頂点xとyについて、ビット演算とテーブル参照を組み合わせることで、 B がxとyの不足にどれだけ寄与しているかを定数時間で数えることができます。このサブルーチンを使用して、アルゴリズムは以下のステップを実行します。  

  • 頂点の任意のパーティションからブロックを作成し、各ブロック内の各頂点の隣接頂点を表す数値を見つけます。
  • ブロックカウント サブルーチンを使用して、すべての隣接する頂点のペアの不足を計算します。
  • すべての頂点が削除されるまで、次の手順を繰り返します。
    • 隣接ペアのうち、不足数が最大でlog  nであり、かつこの集合がまだ構築されていないすべてのペアについて、不足集合を構築する。初期ブロックシステムを用いることで、この構築を高速化できる。
    • 次の手順をn回繰り返します。
      • 構築されているが空の欠損集合を持つペア( x , y )を探す。そのようなペアが存在しない場合、グラフは cop-win ではないため、アルゴリズムを中止する。
      • 頂点xを削除
      • x を、それが属するすべての構築された不足セットから削除します。
    • 削除されたlog n個の頂点と、このブロック内の他のすべての頂点の隣接関係を表す数値のブロックを構築します。
    • この 1 つのブロックでブロック カウント サブルーチンを使用して、すべてのエッジの不足を更新します。

スピンラッドはこのアルゴリズムにかかる総時間をO ( n3 / logn  )と述べている。[13]

無限グラフでは

警官勝利グラフを含むアルゴリズム問題の計算可能性は、無限グラフについても研究されてきた。無限グラフの場合、計算可能な可算無限グラフを構築することが可能であり、そのグラフ上では全知の強盗は常にどの警官からも逃れることができるが、そのような戦略に従うアルゴリズムは存在しない。これらのグラフは、頂点ごとに有限個の辺を持つ無限木となることさえある。ケーニッヒの補題によれば、そのような木には無限の経路が必ず存在し、全知の強盗はこの経路に沿って警官から離れて歩けば勝つことができるが、その経路はアルゴリズムでは見つけることができない。その代わり、強盗の動きを選択するためのあらゆるアルゴリズムは、強盗に向かう唯一の経路に沿って木内を歩くだけの警官によって打ち負かされる可能性がある。同様に、計算可能な可算無限の警官勝利グラフを構築することも可能である。このグラフでは、全知の警官は常に有限回の手で終了する勝利戦略を持っているが、この戦略に従うアルゴリズムは存在しない。このようなグラフでは、警官の手を選択するためのあらゆるアルゴリズムは、強盗によって無期限に回避される可能性がある。[14]

このグラフでは、uは普遍頂点である。つまり、他のすべての頂点に隣接している。

有限弦グラフはすべて分解可能グラフであり、弦グラフのすべての消去順序（各頂点の後続頂点がクリークを形成する頂点の順序）は有効な分解順序である。しかし、無限弦グラフ、さらには直径2の無限弦グラフであっても、cop-winではない。[15] [16]他の種類のグラフでは、有限グラフが存在しない場合でも、その種類の無限cop-winグラフが存在する可能性がある。例えば、これは完全グラフではない頂点推移グラフに当てはまる。[17]

グラフにおける普遍頂点とは、他のすべての頂点に隣接する頂点uである。グラフが普遍頂点を持つ場合、そのグラフは解体可能である。なぜなら、他のすべての頂点は普遍頂点によって支配されており、普遍頂点を最後に置く頂点順序は有効な解体順序だからである。逆に、ほとんどすべての解体可能なグラフは普遍頂点を持つ。つまり、n頂点の解体可能なグラフ全体の中で、普遍頂点を持つグラフの割合は、nが無限大に近づくにつれて極限的に1に近づく。[18]

単純な多角形の可視グラフは常に警官勝利となる。これは多角形の頂点から定義されるグラフであり、2つの頂点が多角形の外側を通らない線分で結ばれる場合、辺が存在する。（特に、多角形内で隣接する頂点はグラフ内でも隣接する。）警官と強盗が頂点間ではなく多角形内の直線上を移動できる場合でも、警官は常に強盗への最短経路の最初のステップを移動することで勝利することができる。このような移動は多角形の一部を遮断し、強盗はそこに戻って到達することができない。警官が頂点から出発し、強盗が頂点間の移動に制限されている場合、この戦略は警官を頂点に制限するため、可視グラフにおいて有効な勝利戦略となる。[19]

5 つの頂点を持つホイール グラフは、cop-win ですが、遺伝的に cop-win ではありません。

遺伝的に cop-win なグラフとは、すべての等長部分グラフ ( の任意の 2 つの頂点について、で測ったそれらの距離が で測ったそれらの距離と同じである部分グラフ) が cop-win であるグラフです。これはすべての cop-win グラフに当てはまるわけではありません。たとえば、5 つの頂点を持つホイール グラフは cop-win ですが、 cop-win ではない等長 4 サイクルを含みます。したがって、このホイール グラフは遺伝的に cop-win ではありません。遺伝的に cop-win なグラフは、ブリッジ グラフ、つまり長さが 4 以上のサイクルすべてにショートカット (サイクル内よりもグラフ内の方が近い頂点のペア) があるグラフと同じです。[20] cop-win グラフが遺伝的に cop-win なのは、4 サイクルも 5 サイクルも誘導サイクルとして持たない場合のみです。遺伝的にcop-winなグラフの場合、幅優先走査の逆順は有効な解体順序であり、そこから任意の頂点を解体順序の最後の頂点として選択できることがわかります。[21] H ⊆ G {\displaystyle H\subseteq G} H {\displaystyle H} G {\displaystyle G} H {\displaystyle H}

警官の数が多い同様のゲームを使って、グラフの警官数、つまりゲームに勝つために必要な最小の警官数を定義することができる。警官勝利グラフは、まさに警官数が1のグラフである。 [22]ボナトとノワコウスキーは、与えられたグラフをプレイフィールドとして、パックマンプレイヤーを負けさせるために必要なゴーストの数としてこのゲームを直感的に説明している。 [23]警官数を定義するために使用されるゲームは、ツリー幅の1つの定義で使用される別の警官と強盗のゲームとは区別する必要がある。このゲームでは、警官はグラフのエッジに沿って移動する必要はなく、任意の頂点に移動できる。[24]

歴史

警官が一人いるゲームと、そこから定義される警官勝利グラフは、Quilliot (1978) によって導入された。[25] [26]もう1つの初期の参考文献は Nowakowski & Winkler (1983) の研究で、G. Gabor によってこのゲームが紹介された。[2] [26]警官が複数いるゲームと、そこから定義される警官の数は、Aigner & Fromme (1984) によって初めて研究された。[22] [26]

参考文献

  1. ^ ボナト、アンソニー; ノワコウスキー、リチャード・J. (2011) 「グラフ上の警官と強盗のゲーム」、学生数学図書館、第61巻、プロビデンス、ロードアイランド州：アメリカ数学会、doi :10.1090/stml/061、ISBN 978-0-8218-5347-4、MR  2830217
  2. ^ abcdefghi Nowakowski, Richard; Winkler, Peter (1983)、「グラフにおける頂点間の追跡」、離散数学、43 ( 2–3 ): 235– 239、doi : 10.1016/0012-365X(83)90160-7、MR  0685631
  3. ^ ab Chepoi, Victor (1998)、「距離保存と支配消去順序について」、SIAM Journal on Discrete Mathematics、11 (3): 414– 436、doi :10.1137/S0895480195291230、MR  1628110
  4. ^ Bonato & Nowakowski (2011)、定理 2.3、32 ページ。
  5. ^ Bonato, A.; Golovach, P.; Hahn, G.; Kratochvíl, J. (2009)、「グラフのキャプチャ時間」、離散数学、309 (18): 5588– 5595、doi : 10.1016/j.disc.2008.04.004、MR  2567962
  6. ^ Gavenčiak, Tomáš (2010)、「最大捕捉時間を持つCop-winグラフ」、離散数学、310 ( 10– 11): 1557– 1563、doi : 10.1016/j.disc.2010.01.015、MR  2601265
  7. ^ Bonato & Nowakowski (2011)、p. 36.
  8. ^ Bonato & Nowakowski (2011)、補題 2.1、31 ページ。
  9. ^ Bonato & Nowakowski (2011)、定理 2.2、32 ページ。
  10. ^ Bonato & Nowakowski (2011)、定理 2.8、43 ページ。
  11. ^ パスの強積がcop-winであるという事実については、Nowakowski & Winkler (1983) を参照。キンググラフがパスの強積であるという事実については、Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005)、「平面グラフと関連グラフの2色対色」(PDF)、 2005 International Conference on Analysis of Algorithms、Discrete Mathematics & Theoretical Computer Science Proceedings、Nancy: Association for Discrete Mathematics & Theoretical Computer Science、pp. 335– 341、MR  2193130を参照。 
  12. ^ Lin, Min Chih; Soulignac, Francisco J.; Szwarcfiter, Jayme L. (2012)、「Arboricity、h指数、および動的アルゴリズム」、理論計算機科学、426– 427: 75– 90、arXiv : 1005.2211、doi :10.1016/j.tcs.2011.12.006、MR  2891574、S2CID  15827218
  13. ^ ab Spinrad, Jeremy P. (2004)、「準三角グラフの認識」、離散応用数学、138 ( 1–2 ): 203– 213、doi : 10.1016/S0166-218X(03)00295-6、MR  2057611
  14. ^ スタール、レイチェル・D.（2021年9月）「グラフ上の警官と強盗のゲームと計算可能性」、Archive for Mathematical Logic、61（3–4）：373–397、doi：10.1007/s00153-021-00794-3、S2CID  244214571
  15. ^ Hahn, Geňa; Laviolette, François; Sauer, Norbert; Woodrow, Robert E. (2002)、「警官勝利グラフについて」、離散数学、258 ( 1–3 ): 27– 41、doi : 10.1016/S0012-365X(02)00260-1、MR  2002070
  16. ^ Bonato & Nowakowski (2011)、セクション7.4、無限弦グラフ、pp. 178–182。
  17. ^ Bonato & Nowakowski (2011)、セクション7.5、頂点推移的cop-winグラフ、pp. 182–187。
  18. ^ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012)、「ほ​​とんどすべてのcop-winグラフはユニバーサル頂点を含む」、Discrete Mathematics、312 (10): 1652– 1657、doi : 10.1016/j.disc.2012.02.018、MR  2901161
  19. ^ Lubiw, Anna ; Snoeyink, Jack ; Vosoughpour, Hamideh (2017)、「可視グラフ、解体可能性、そして警官と強盗のゲーム」、計算幾何学、66 : 14–27、arXiv : 1601.01298、doi :10.1016/j.comgeo.2017.07.001、MR  3693353
  20. ^ Anstee, RP; Farber, M. (1988)、「ブリッジグラフとcop-winグラフについて」、Journal of Combinatorial Theory、シリーズB、44 (1): 22– 28、doi : 10.1016/0095-8956(88)90093-7、MR  0923263
  21. ^ Chepoi, Victor (1997)、「ブリッジグラフはcop-winグラフである：アルゴリズム的証明」、Journal of Combinatorial Theory、シリーズB、69 (1): 97– 100、doi : 10.1006/jctb.1996.1726、MR  1426753
  22. ^ ab Aigner, M.; Fromme, M. (1984)、「警官と強盗のゲーム」、離散応用数学、8 (1): 1– 11、doi : 10.1016/0166-218X(84)90073-8、MR  0739593
  23. ^ Bonato & Nowakowski (2011)、1–3 ページ。
  24. ^ シーモア、ポール・D. ;トーマス、ロビン(1993)、「グラフ探索とツリー幅の最小最大定理」、Journal of Combinatorial Theory、シリーズB、58 (1): 22– 33、doi : 10.1006/jctb.1993.1027
  25. ^ Quilliot、Alain (1978)、Jeux et pointes fixes sur lesgraphes [ゲームとグラフ上の固定点]、Thèse de 3ème Cycle (フランス語)、ピエール・マリー・キュリー大学、 131–145ページ 、Bonato & Nowakowski が引用したもの (2011)
  26. ^ abc ボナート & ノヴァコウスキー (2011)、p. 4.
  • 分解可能なグラフ、グラフクラスとその包含に関する情報システム
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cop-win_graph&oldid=1285799932"