リーチビリティ

グラフ内の1つの頂点が別の頂点から到達可能かどうか

グラフ理論において、到達可能性とは、グラフ内のある頂点から別の頂点へ到達できる能力を指します。ある頂点が別の頂点に到達できる（つまり、から到達可能である）ためには、隣接する頂点の列（つまり、ウォーク）が存在し、その列が で始まり で終わる必要があります ${\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}$

グラフは、各レベルが単一の頂点に縮約されたものである一連の有向グラフとして再表現されます。すべての有向グラフは最大で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つのディパスになります。このディパスの集合を とします。このようなセパレータが常に見つかるという証明は、リプトンとタージャンの平面セパレータ定理に関連しており、これらのセパレータは線形時間で見つけることができます。 ${\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})}$

亀田のアルゴリズム

とを加えた、亀田法に適した有向グラフ ${\displaystyle s}$ ${\displaystyle t}$

亀田のアルゴリズムを実行した後の上記と同じグラフ。各頂点のDFSラベルを表示している。

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}}$

到達可能性クエリに関連するもう一つの問題は、グラフの一部が変更された場合に、到達可能性関係の変更を迅速に再計算する必要があることです。例えば、これはガベージコレクションに関連する懸念事項であり、ガベージコレクションでは、メモリの回収（再割り当てのため）と実行中のアプリケーションのパフォーマンスへの配慮のバランスを取る必要があります。

参照

• ガモイド
• st-連結性

参考文献

1. スキエナ、スティーブン・S.（2011）、「15.5 推移的閉包と縮約」、アルゴリズム設計マニュアル（第2版）、シュプリンガー、pp.  495– 497、ISBN 9781848000698。
2. コーン、ポール・モーリッツ（2003年）、Basic Algebra: Groups, Rings, and Fields、シュプリンガー、p. 17、ISBN 9781852335878。
3. シュミット、ガンサー（2010年）、関係数学、数学とその応用百科事典、第132巻、ケンブリッジ大学出版局、77ページ、ISBN 9780521762687。
4. ガースティング、ジュディス・L. (2006)、『コンピュータサイエンスのための数学的構造（第6版）』、マクミラン、519ページ、ISBN 9780716768647。
5. コーメン、トーマス・H.、レイサーソン、チャールズ・E.、リベスト、ロナルド・L.、スタイン、クリフォード(2001)、「有向グラフの推移閉包」『アルゴリズム入門』 （第2版）、MITプレスおよびマグロウヒル、  632～ 634ページ、ISBN 0-262-03293-7。
6. Thorup, Mikkel (2004)、「平面有向グラフにおける到達可能性と近似距離のためのコンパクトオラクル」、Journal of the ACM、51 (6): 993–1024、doi :10.1145/1039488.1039493、MR  2145261、S2CID  18864647。
7. 亀田, 孝文 (1975), 「平面有向グラフにおける到達可能性のベクトル表現について」,情報処理レター, 3 (3): 75– 77, doi :10.1016/0020-0190(75)90019-8。
8. デメトレスク、カミル;ミッケル・ソーラップ;チョードリー、レザウル・アラム。 Ramachandran、Vijaya (2008)、「障害が発生したノードまたはリンクを回避する距離のオラクル」、SIAM Journal on Computing、37 (5): 1299–1318、CiteSeerX 10.1.1.329.5435、doi :10.1137/S0097539705429847、MR  2386269 。
9. Halftermeyer, Pierre, ネットワークの接続性と緊急時計画のためのコンパクトなラベル付けスキーム、ボルドー大学。

「https://en.wikipedia.org/w/index.php?title=Reachability&oldid=1318693359」より取得