到達可能性

グラフ理論において、到達可能性とは、グラフ内のある頂点から別の頂点へ到達する能力を指します。で始まり で終わる隣接する頂点のシーケンス(つまり、ウォーク) が存在する場合、頂点は頂点に到達できます(から到達可能です) 。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle t}$${\displaystyle s}$${\displaystyle s}$${\displaystyle t}$

無向グラフでは、グラフの連結成分を識別することによって、すべての頂点ペア間の到達可能性を判断できます。このようなグラフの任意の頂点ペアは、同じ連結成分に属している場合にのみ、互いに到達できます。したがって、このようなグラフでは、到達可能性は対称です (到達かつ到達)。無向グラフの連結成分は線形時間で識別できます。この記事の残りの部分では、有向グラフ(ちなみに、対称である必要はありません) のペアごとの到達可能性を判断するという、より困難な問題に焦点を当てます。${\displaystyle s}$${\displaystyle t}$ ${\displaystyle t}$${\displaystyle s}$

頂点集合と辺集合 を持つ有向グラフ の場合、の到達可能性関係はの推移閉包、つまり 内のすべての頂点の順序付きペアの集合であり、 に対して辺が内のすべてのに対して存在するような頂点の列が存在する集合です。^[1]${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle G}$${\displaystyle E}$${\displaystyle (s,t)}$${\displaystyle V}$${\displaystyle v_{0}=s,v_{1},v_{2},...,v_{k}=t}$${\displaystyle (v_{i-1},v_{i})}$${\displaystyle E}$${\displaystyle 1\leq i\leq k}$

が非巡回である場合、その到達可能性関係は半順序です。任意の半順序は、たとえばその推移的簡約の到達可能性関係として、このように定義できます。^[2]このことの注目すべき結果は、半順序は反対称であるため、 が に到達できる場合、 は に到達できないことがわかるということです。直感的には、からに移動して に戻ることができる場合、 にはサイクルが含まれ、非巡回であることと矛盾します。が有向であるが非巡回ではない場合(つまり、少なくとも 1 つのサイクルを含む場合)、その到達可能性関係は半順序ではなく前順序に対応します。^[3]${\displaystyle G}$${\displaystyle s}$${\displaystyle t}$${\displaystyle t}$ ${\displaystyle s}$${\displaystyle s}$${\displaystyle t}$${\displaystyle s}$${\displaystyle G}$${\displaystyle G}$

到達可能性を決定するアルゴリズムは、前処理を必要とするものと必要としないものの 2 つのクラスに分類されます。

実行するクエリが1つ（または少数）だけの場合は、より複雑なデータ構造の使用を控え、目的のペアの到達可能性を直接計算する方が効率的です。これは、幅優先探索や反復深化深さ優先探索などのアルゴリズムを使用して線形時間で実行できます。^[4]

多数のクエリを実行する場合は、より高度な方法を使用できます。方法の正確な選択は、分析するグラフの性質によって異なります。前処理時間と追加のストレージ スペースと引き換えに、任意の頂点のペアの到達可能性クエリに最短時間で回答できるデータ構造を作成できます。3 つの異なる、より特殊な状況に対応する 3 つの異なるアルゴリズムとデータ構造を以下に概説します。 ${\displaystyle O(1)}$

フロイド・ワーシャルアルゴリズム^[5]は、任意の有向グラフの推移閉包を計算するために使用することができ、上記の定義のように到達可能性関係を生じさせる。

このアルゴリズムは、最悪の場合、時間とスペースを必要とします。このアルゴリズムは、すべての頂点ペア間の最短経路距離も計算するため、到達可能性だけに注目しているわけではありません。負のサイクルを含むグラフの場合、最短経路は定義されない可能性がありますが、ペア間の到達可能性は依然として記録できます。 ${\displaystyle O(|V|^{3})}$${\displaystyle O(|V|^{2})}$

平面 有向グラフの場合、 2004年にMikkel Thorupによって説明されたように、はるかに高速な方法が利用可能です。^[6]この方法は、前処理時間を費やしてサイズのデータ​​構造を作成した後、平面グラフ上の到達可能性クエリに時間内に回答できます。このアルゴリズムは、ルート情報だけでなく、おおよその最短パス距離も提供できます。 ${\displaystyle O(1)}$${\displaystyle O(n\log {n})}$${\displaystyle O(n\log {n})}$

全体的なアプローチとしては、各頂点に、いわゆるセパレータ パスの比較的小さなセットを関連付け、頂点から他の頂点へのパスは、またはに関連付けられたセパレータの少なくとも 1 つを通過するようにすることです。到達可能性に関連するセクションの概要は次のとおりです。 ${\displaystyle v}$${\displaystyle w}$${\displaystyle v}$${\displaystyle w}$

グラフ が与えられると、アルゴリズムは、任意の頂点 から始めて頂点を層に編成することから始めます。層は、まず前のステップから到達可能なすべての頂点( から開始) を考慮し、次に前のステップに到達するすべての頂点を考慮するという交互のステップで構築され、すべての頂点が層に割り当てられるまで続きます。層の構築により、すべての頂点は最大で 2 つの層に現れ、 内のすべての有向パス、つまり dipath は、 2 つの隣接する層と内に含まれます。を最後に作成された層、つまり となるの最小値とします。 ${\displaystyle G}$${\displaystyle v_{0}}$${\displaystyle v_{0}}$${\displaystyle G}$${\displaystyle L_{i}}$${\displaystyle L_{i+1}}$${\displaystyle k}$${\displaystyle k}$${\displaystyle \bigcup _{i=0}^{k}L_{i}=V}$

次に、グラフは、各および の一連の有向グラフとして再表現されます。 は、以前のすべてのレベルを1 つの頂点に縮約したものです。すべての有向グラフは最大で 2 つの連続する層に出現し、各 は2 つの連続する層によって形成されるため、 のすべての有向グラフは、少なくとも 1 つの(最大で 2 つの連続するグラフ) に完全に出現します。${\displaystyle G_{0},G_{1},\ldots ,G_{k-1}}$${\displaystyle G_{i}=r_{i}\cup L_{i}\cup L_{i+1}}$${\displaystyle r_{i}}$${\displaystyle L_{0}\ldots L_{i-1}}$${\displaystyle G_{i}}$${\displaystyle G}$${\displaystyle G_{i}}$

各 について、3 つのセパレータが識別されます。これらを削除すると、グラフは 3 つのコンポーネントに分割され、各コンポーネントには最大で元のグラフの頂点が含まれます。は 2 つの層の反対方向のディパスから構築されるため、各セパレータは最大 2 つのディパスで構成され、セパレータ全体では最大 6 つのディパスになります。 をこのディパスの集合とします。このようなセパレータが常に見つかるという証明は、 Lipton と Tarjan の平面セパレータ定理に関連しており、これらのセパレータは線形時間で見つけることができます。 ${\displaystyle G_{i}}$${\displaystyle 1/2}$${\displaystyle G_{i}}$${\displaystyle S}$

各 について、 の有向性により、パスの始めから終わりまでの頂点の自然なインデックス付けが可能になります。内の各頂点について、によって到達可能な内の最初の頂点と、に到達する内の最後の頂点を見つけます。つまり、から にどれだけ早く到達できるか、 にどれだけ長く留まって に戻れるかを調べています。この情報は各 とともに保存されます。次に、 と の任意の頂点ペアについて、が に からに接続するよりも早く に接続する場合、はを介し​​て到達できます。 ${\displaystyle Q\in S}$${\displaystyle Q}$${\displaystyle v}$${\displaystyle G_{i}}$${\displaystyle Q}$${\displaystyle v}$${\displaystyle Q}$${\displaystyle v}$${\displaystyle Q}$${\displaystyle v}$${\displaystyle Q}$${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle w}$${\displaystyle u}$${\displaystyle w}$ ${\displaystyle Q}$${\displaystyle u}$${\displaystyle Q}$${\displaystyle w}$${\displaystyle Q}$

再帰の各ステップで、すべての頂点に上記のようにラベルが付けられ、 が構築されます 。この再帰は対数的な深さを持つため、頂点ごとに合計 の 追加情報が格納されます。この時点から、到達可能性の対数時間のクエリは、共通の適切な についてラベルの各ペアを調べるのと同じくらい簡単です。元の論文では、クエリ時間を まで調整するように取り組んでいます。 ${\displaystyle G_{0}\ldots ,G_{k}}$${\displaystyle O(\log {n})}$${\displaystyle Q}$${\displaystyle O(1)}$

この方法の分析をまとめると、まず、レイヤ化アプローチでは頂点を分割して、各頂点が だけ考慮されるということを考慮します 。アルゴリズムのセパレータ フェーズでは、グラフを最大で元のグラフのサイズのコンポーネントに分割し、対数的な再帰深度を実現します。再帰の各レベルでは、セパレータと頂点間の可能な接続を識別するために線形作業のみが必要です。全体的な結果は、各頂点に追加情報のみが 保存される前処理時間です。 ${\displaystyle O(1)}$${\displaystyle 1/2}$${\displaystyle O(n\log n)}$${\displaystyle O(\log {n})}$

1975 年に T. Kameda が提案した、さらに高速な前処理方法^{[7]は、グラフが}平面で非巡回であり、さらに次の特性も示す 場合に使用できます。つまり、すべての 0入次数頂点とすべての 0出次数頂点が同じ面(多くの場合、外面と想定されます) に表示され、その面の境界を 2 つの部分に分割して、すべての 0 入次数頂点が一方の部分に表示され、すべての 0 出次数頂点がもう一方の部分に表示される (つまり、2 種類の頂点が交互に表示されない) ようにすることができます。

がこれらの特性を示す場合、時間のみでグラフを前処理し 、頂点ごとに追加ビットのみを保存して、単純な比較で任意 の頂点ペアの到達可能性クエリに時間内に回答できます。${\displaystyle G}$${\displaystyle O(n)}$${\displaystyle O(\log {n})}$${\displaystyle O(1)}$

前処理では、次の手順を実行します。0入次数の頂点ごとに辺を持つ新しい頂点と、 0 出次数の頂点ごとに辺を持つ別の新しい頂点を追加します。 の特性により、平面性を維持しながらこれを行うことができます。つまり、これらの追加後も辺の交差はありません。 各頂点について、隣接 (出辺) のリストをグラフの平面性の順序で格納します (たとえば、グラフの埋め込みに対して時計回り)。 次に、カウンタを初期化し、 から深さ優先探索を開始します。 この探索中、各頂点の隣接リストは、必要に応じて左から右に参照されます。 頂点が探索のスタックからポップされると、値 のラベルが付けられ、 がデクリメントされます。は常に値 のラベルが付けられ、 は常に のラベルが付けられることに注意してください。次に深さ優先のトラバーサルが繰り返されますが、今回は各頂点の隣接リストが右から左に訪問されます。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle G}$${\displaystyle i=n+1}$${\displaystyle s}$${\displaystyle i}$${\displaystyle i}$${\displaystyle t}$${\displaystyle n+1}$${\displaystyle s}$${\displaystyle 0}$

完了すると、および、およびそれらの接続辺 が削除されます。残りの各頂点には、 から までの値を持つ 2 次元ラベルが格納されます。2つの頂点および、およびそのラベル およびが与えられている場合、 、 、および の場合にのみ、またはより確実に小さい1 つの成分またはが存在すると言えます。 ${\displaystyle s}$${\displaystyle t}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle u}$${\displaystyle v}$${\displaystyle L(u)=(a_{1},a_{2})}$${\displaystyle L(v)=(b_{1},b_{2})}$${\displaystyle L(u)<L(v)}$${\displaystyle a_{1}\leq b_{1}}$${\displaystyle a_{2}\leq b_{2}}$${\displaystyle a_{1}}$${\displaystyle a_{2}}$${\displaystyle b_{1}}$${\displaystyle b_{2}}$

この方法の主な結果は、 の場合にのみから に到達可能であり、これは時間 内に簡単に計算できることを示しています。${\displaystyle v}$${\displaystyle u}$${\displaystyle L(u)<L(v)}$${\displaystyle O(1)}$

関連する問題として、頂点の障害がいくつかある場合の到達可能性クエリを解決するというものがあります。たとえば、「頂点が障害を起こして使用できなくなっても、頂点は頂点に到達できますか？」という問題です。同様の問題では、頂点の障害ではなくエッジの障害、または両者の組み合わせを考慮する場合があります。幅優先探索手法はこのようなクエリでも同様に機能しますが、効率的なオラクルを構築するのはより困難です。^{[8] [9]}${\displaystyle k}$${\displaystyle u}$${\displaystyle v}$${\displaystyle s_{1},s_{2},...,s_{k}}$

到達可能性クエリに関連するもう 1 つの問題は、グラフの一部が変更されたときに、到達可能性関係の変更を迅速に再計算することです。たとえば、これは、メモリの再利用 (再割り当てが可能になるように) と実行中のアプリケーションのパフォーマンスの問題とのバランスを取る必要があるガベージ コレクションに関連する問題です。

• ガモイド
• st -接続性