Loading article…
グラフ理論 において、警官勝利グラフとは、追跡者（警官）が強盗との追跡回避ゲームで常に勝利できる無向グラフのことである。プレイヤーは交互にターンを行い、グラフのエッジに沿って移動するか、その場にとどまるかを選択し、警官が強盗の頂点に到達するまでゲームを続ける。[ 1 ]有限警官勝利グラフは、支配される頂点（閉じた近傍が別の頂点の近傍の部分集合である頂点）を繰り返し削除することによって解体したり、そのような頂点を繰り返し追加することによって構築したりできるため、解体可能グラフまたは構築可能グラフとも呼ばれる。警官勝利グラフは、解体順序を構築する貪欲アルゴリズムによって多項式時間で認識できる。これには、弦グラフや、普遍頂点を含むグラフが含まれる。
警官勝利グラフは、警官と泥棒の2人のプレイヤーが、与えられた無向グラフの異なる初期頂点に配置される追跡回避ゲームによって定義できます。警官が最初に初期頂点を選択し、次に泥棒が選択します。次に、警官が最初にプレイし、交互にプレイします。各プレイヤーのターンでは、プレイヤーは隣接する頂点に移動するか、その場にとどまることができます。警官が泥棒と同じ頂点でターンを終了できればゲームは終了し、警官が勝ちます。泥棒は警官から永久に逃げ続けることで勝ちます。警官勝利グラフは、プレイヤーが開始位置を選択してこのように移動する場合、警官が常に勝利を強制できるという性質を持つグラフです。無向グラフが警官勝利グラフでない場合、それは泥棒勝利グラフと呼ばれます。[ 2 ]
与えられたグラフにおける頂点vの閉近傍 N [ v ]は、 v自身とvに隣接する他のすべての頂点からなる頂点の集合です。頂点vは、 N [ v ] ⊂ N [ w ]のときに、別の頂点wによって支配されていると言われます。つまり、vとwは隣接しており、vの他のすべての近傍もwの近傍です。[ 3 ] NowakowskiとWinkler (1983)は、別の頂点によって支配されている頂点を既約頂点と呼んでいます。[ 2 ]
与えられたグラフの解体順序または支配排除順序とは、頂点をこの順序で1つずつ削除していくと、各頂点（最後の頂点を除く）が削除される時点で支配されるような頂点の順序のことである。グラフは、解体順序を持つ場合に限り解体可能である。 [ 2 ] [ 3 ]
有限分解可能グラフはすべて警官が勝つ。これは数学的帰納法によって証明でき、基本ケースとして頂点が 1 つのグラフ (警官が自明に勝つ) がある。より大きなグラフの場合、v を任意の支配頂点とする。帰納法の仮説により、警官はv を取り除いて形成されたグラフ上で勝利戦略を持ち、泥棒が実際にvにいるときはいつでも、泥棒がv を支配する頂点にいると仮定することで、元のグラフ上で同じ戦略に従うことができる。この戦略に従うと、実際にゲームに勝つか、泥棒がvにいて警官が支配頂点にいる位置になり、そこから警官はあと 1 手で勝つことができる。[ 2 ] [ 4 ] n個の頂点を持つグラフでこの帰納的戦略に従う警官は、開始位置に関係なく、最大でn手で勝つことができる。警官の開始位置を慎重に選択することで、同じ考え方を用いて、n頂点グラフでは警官が最大n − 4手で勝利を強制できることを証明できる。[ 5 ] [ 6 ] [ 7 ]
逆に、警官が勝つグラフには必ず支配される頂点が存在する。なぜなら、支配される頂点のないグラフでは、強盗がまだ負けていない場合、警官に隣接していない位置に安全に移動できる位置があり、強盗は各ターンでこれらの安全な移動のいずれかを行うことでゲームを無限に続けることができるからである。[ 2 ] [ 8 ]さらに、vが警官が勝つグラフの支配される頂点である場合、v を削除すると別の警官が勝つグラフが生成されなければならない。そうでなければ、強盗はその部分グラフ内でプレイし、警官が実際にはvにいるときに、警官がvを支配する頂点にいると偽って、決して捕まらないことができるからである。これらの 2 つの原理から帰納的に、すべての有限の警官が勝つグラフは分解可能であることがわかる。[ 2 ] [ 9 ]
数学的対象の族は、その族のメンバーを組み合わせると常にその族の別のメンバーが生成されるとき、一連の演算の下で閉じていると言われます。その意味で、警官勝利グラフの族は、グラフの強い積の下で閉じています。強い積の各頂点は、2 つの因子グラフのそれぞれの頂点のペアに対応します。警官は、まず、これら 2 つの因子グラフのいずれかで勝利を目指してプレイし、最初のコンポーネントが強盗と同じペアに到達することで、2 つの警官勝利グラフの強い積で勝利することができます。次に、最初のコンポーネントが強盗と同じペアにとどまりながら、警官は 2 つの因子の 2 番目の因子で勝利を目指してプレイすることができます。[ 2 ] [ 10 ]例えば、 2 つのパス グラフの強い積であるキングのグラフは、警官勝利です。このグラフでは、頂点はチェス盤のマス目に対応しており、警官と泥棒はどちらもチェスのキングのように、水平、垂直、または斜めに隣接するマス目に移動します。警官の積ベースの戦略は、まず泥棒と同じ行に移動し、次に各ステップで泥棒と同じ行にとどまりながら、泥棒の列に向かって移動することです。[ 11 ]
警官勝利グラフの すべての誘導部分グラフが警官勝利であるとは限りません。ただし、特定の特別な誘導部分グラフは警官勝利のままです。Nowakowski & Winkler (1983)は、グラフGをその誘導部分グラフHのいずれかに引き戻すことを、 Gの頂点からHの頂点への写像であり、 Hの各頂点をそれ自身に写像し、Gの隣接する頂点の各ペアを互いに同じ頂点またはHの隣接する頂点のペアに写像するものと定義しています。すると、警官勝利グラフの族は引き戻しに関して閉じられます。これは、警官がGでのゲームをシミュレートすることでHで勝つことができるためです。Gでの勝利戦略が警官にその場にとどまるか、端点がHの同じ頂点に写像されるエッジをたどることを要求する場合、警官はHでその場にとどまります。そして他のすべてのケースでは、警官はGの勝ちエッジの撤回によるイメージであるHのエッジに従います。[ 2 ]
グラフが警官勝利であるかどうかをチェックし、もし警官が勝利できるようなグラフの解体手順を見つけるための様々な戦略が知られている。これらには、貪欲アルゴリズムや、頂点の共有隣接点の数を数えることに基づくより複雑なアルゴリズムなどが含まれる。
解体順序は、支配されている頂点を繰り返し見つけて削除する単純な貪欲アルゴリズムによって見つけることができます。このプロセスは、グラフがcop-winである場合に限り、グラフを単一の頂点に縮小することで成功します。したがって、この方法は、解体順序を見つけるアルゴリズムを提供するだけでなく、与えられたグラフがcop-winであるかどうかをテストするアルゴリズムも提供します。このアルゴリズムが削除する支配されている頂点を見つける1つの方法は、次の手順を実行することです。
n個の頂点、m個のエッジ、および縮退度dを持つグラフでは、このプロセスはO ( dm )の時間で実行できます 。[ 12 ]
Spinrad (2004)による、より複雑な別のアルゴリズムでは、隣接する頂点のペア( x、y )ごとに、欠損と呼ばれる数値を維持します。この欠損は、 xの隣接頂点のうち、 yの隣接頂点ではない頂点の数をカウントします。他の頂点が削除された後、この数値がゼロになった場合、x はyに支配されているため、削除される可能性があります。実際の欠損セット( xの隣接頂点のうち、 yの隣接頂点ではない頂点)は、欠損が小さいペア ( x、y )に対してのみ構築および維持されます。 [ 13 ]
スピンラッドのアルゴリズムは、計算を高速化するために、log 2 n 個の頂点からなる小さなブロック内の隣接点を数えるサブルーチンを使用します。Bがアルゴリズムによってブロックとして選択された頂点の集合である場合、他の任意の頂点について、 B内のその頂点の隣接点の集合は、log 2 nビットのバイナリ数として表現できます。これらの数により、アルゴリズムは、任意の 2 つの頂点xとyについて、ビット演算とテーブル参照の組み合わせによって、定数時間で、B がxとyの不足にどれだけ寄与しているかを数えることができます。このサブルーチンを使用して、アルゴリズムは次の手順を実行します。
Spinradはこのアルゴリズムの合計時間をO ( n3 / log n ) と述べている。[ 13 ]
警官が勝つグラフを含むアルゴリズム問題の計算可能性は、無限グラフについても研究されてきた。無限グラフの場合、計算可能な可算無限グラフを構築することが可能であり、そのグラフ上では全知の泥棒はどんな警官からも常に逃れることができるが、この戦略に従うアルゴリズムは存在しない。これらのグラフは、頂点ごとに有限個のエッジを持つ無限木である場合もある。ケーニッヒの補題によれば、そのような木には無限の経路が存在し、全知の泥棒はこの経路に沿って警官から逃げることで勝つことができるが、その経路はアルゴリズムでは見つけることができない。その代わりに、泥棒の移動を選択するすべてのアルゴリズムは、木の中で泥棒に向かう唯一の経路に沿って歩く警官によって打ち負かされる可能性がある。同様に、計算可能な可算無限の警官勝利グラフを構築することも可能であり、そのグラフ上では、全知の警官は常に有限回の移動で終了する勝利戦略を持つが、その戦略に従うアルゴリズムは存在しない。このようなグラフ上では、警官の移動を選択するすべてのアルゴリズムは、強盗によって無限に回避される可能性がある。[ 14 ]
すべての有限弦グラフは分解可能なグラフであり、弦グラフのすべての消去順序（各頂点の後の隣接頂点がクリークを形成する頂点の順序）は有効な分解順序です。しかし、無限弦グラフ、さらには直径が2 の無限弦グラフでも、cop-win ではないものがあります。 [ 15 ] [ 16 ]他のタイプのグラフでは、有限の cop-win グラフが存在しない場合でも、そのタイプの無限 cop-win グラフが存在する場合があります。たとえば、これは完全グラフではない頂点推移グラフの場合に当てはまります。[ 17 ]
グラフにおける普遍頂点とは、他のすべての頂点に隣接する頂点 u のことである。グラフが普遍頂点を持つ場合、他のすべての頂点は普遍頂点によって支配されるため、そのグラフは解体可能である。普遍頂点を最後に配置する頂点順序は有効な解体順序である。逆に、n個の頂点を持つ解体可能なグラフのうち、普遍頂点を持つグラフの割合は、n が無限大に近づくにつれて 1 に収束するという意味で、ほとんどすべての解体可能なグラフは普遍頂点を持つ。[ 18 ]
単純な多角形の可視グラフは常に警官が勝つ。これは多角形の頂点から定義されるグラフで、2つの頂点が多角形の外側を通らない線分で接続できる場合にエッジが存在する。（特に、多角形で隣接する頂点はグラフでも隣接している。）警官と泥棒が多角形内の直線セグメント上を移動できる場合でも、頂点から頂点へ移動できない場合でも、警官は常に泥棒への最短経路の最初のステップに移動することで勝つことができる。このような移動によって、泥棒が戻ることのできない多角形の一部が切り取られる。警官が頂点から出発し、泥棒が頂点間の移動に制限されている場合、この戦略は警官の移動範囲も頂点に制限するため、可視グラフにとって有効な勝利戦略となる。[ 19 ]
遺伝的に警官が勝つグラフは、すべての等長部分グラフ（部分グラフ）が任意の2つの頂点に対してそれらの間の距離は、 は、2つの間の距離を測定した値と同じです。）は cop-win です。これはすべての cop-win グラフに当てはまるわけではありません。たとえば、5 頂点のホイール グラフは cop-win ですが、等長 4 サイクルを含み、これは cop-win ではないため、このホイール グラフは遺伝的に cop-win ではありません。遺伝的に cop-win グラフは、ブリッジ グラフと同じです。ブリッジ グラフとは、長さ 4 以上のすべてのサイクルにショートカット、つまりサイクル内よりもグラフ内で近い頂点のペアが存在するグラフです。[ 20 ] cop-win グラフが遺伝的に cop-win であるのは、誘導サイクルとして 4 サイクルも 5 サイクルも持たない場合のみです。遺伝的に cop-win グラフの場合、任意の幅優先探索の反転は有効な分解順序であり、そこから任意の頂点を分解順序の最後の頂点として選択できることがわかります。[ 21 ]
警官の数が多い同様のゲームは、グラフの警官数、つまりゲームに勝つために必要な警官の最小数を定義するために使用できます。警官勝利グラフは、警官数が 1 に等しいグラフとまったく同じです。 [ 22 ]ボナートとノワコフスキは、このゲームを直感的に、与えられたグラフをプレイフィールドとして使用して、パックマンのプレイヤーを負けさせるのに必要なゴーストの数として説明しています。 [ 23 ]警官数を定義するために使用されるゲームは、ツリー幅の定義の 1 つで使用される別の警官と泥棒のゲームとは区別する必要があります。ツリー幅の定義では、警官はグラフのエッジに沿って移動するのではなく、任意の頂点に移動できます。[ 24 ]
警官が1人だけのゲームと、そこから定義される警官の勝利グラフは、Quilliot (1978)によって導入されました。[ 25 ] [ 26 ]もう1つの初期の参考文献は、G. Gabor からこのゲームを紹介されたNowakowski & Winkler (1983)の研究です。 [ 2 ] [ 26 ]警官が複数いるゲームと、そこから定義される警官の数は、Aigner & Fromme (1984)によって初めて研究されました。[ 22 ] [ 26 ]
