エンタングルメント（グラフ測度）
グラフ理論において、有向グラフのエンタングルメント（絡み合い）とは、グラフのサイクルがどれだけ強く絡み合っているかを表す数値です。これは、n人の警官がグラフの端に沿って逃げる強盗を捕まえようとする数学的なゲームで 定義されます。サイクルランクなどの他のグラフ指標と同様に、パリティゲームなどのアルゴリズムの問題は、有界エンタングルメントを持つグラフ上で効率的に解くことができます。
意味
エンタングルメントゲーム[ 1 ]は、有向グラフG上でn人の警官と強盗が対戦するゲームです。最初は、すべての警官はグラフの外側にいて、強盗は Gの任意の開始頂点vを選択します。さらに、プレイヤーは順番に動きます。各移動で、警官は現在の場所にいるか、現在強盗が占めている頂点に警官の1人を配置します。強盗は、現在の頂点から、辺に沿って、警官が占めていない後続の頂点まで移動する必要があります。強盗は、追従する警官がいない場合は移動する必要があります。強盗が移動できる空いている後続の頂点がない場合、強盗は捕まり、警官が勝ちます。強盗が捕まらない場合、つまりゲームを永遠に続けることができる場合、強盗は勝ちます。
グラフGのエンタングルメント ゲームでn人の警官が勝つが、n − 1 人の警官が負ける 場合、グラフGにはエンタングルメントn があります。
特性と用途
エンタングルメント0と1のグラフは次のように特徴付けられる: [ 1 ]
- Gのエンタングルメントが0であるのは、 Gが非巡回的である 場合のみである。
- Gのエンタングルメントが1 となるのは、 Gが非巡回でない場合であり、Gのあらゆる強連結成分には、それを除去すると成分が非巡回になるノードが存在する場合です。
エンタングルメントは、様相ミュー計算の変数階層が厳密であることを証明する上で重要な概念でもある。[ 2 ]
参考文献
- ^ a b D. BerwangerとE. Grädel、 「エンタングルメント - 有向グラフの複雑さの尺度と論理とゲームへの応用」、LPAR '04の議事録、LNCSの第3452巻、pp. 209–223 (2004)
- ^ D. Berwanger、E. Grädel、G. Lenzi、 「ミュー計算の変数階層は厳密である」、Theory of Computing Systems、第40巻、pp. 437–466 (2007)
外部リンク
エンタングルメントゲームはtPlayでオンラインでプレイできます。
