到達可能性

到達可能性（とうたつかのうせい、）は、グラフ理論において、グラフ内のある頂点から別の頂点に到達できるかどうかを表す概念である。頂点が頂点に到達できる（がから到達可能である）のは、から始まりで終わる隣接する頂点の列（ウォーク）が存在する場合である。

無向グラフにおいては、すべての頂点ペア間の到達可能性は、グラフの連結成分を特定することで判定できる。そのようなグラフでは、2頂点が同じ連結成分に属する場合かつその場合に限り互いに到達可能であるため、到達可能性は対称的である（がに到達できるiff がに到達できる）。無向グラフの連結成分は線形時間で特定できる。本記事の残りでは、より難しい問題である有向グラフ内のすべての頂点ペア間の到達可能性判定に焦点を当てる（なお、有向グラフでは対称性が成り立つとは限らない）。

定義頂点集合と辺集合を持つ有向グラフにおいて、の到達可能性関係とはの推移閉包、すなわち内のすべての辺（）を通る頂点列が存在するような内の順序対の全体集合である.。

が非巡回である場合、その到達可能性関係は半順序となる。逆に任意の半順序は、そのの到達可能性関係として定義できる.。この帰結として重要なのは、半順序は反対称であるため、がに到達できるならばはに到達できないことが分かることである。直観的には、からへ到達しさらにに戻れるとすれば、は閉路を含むこととなり、非巡回性に矛盾する。が有向であるが非巡回でない場合（すなわち少なくとも1つの閉路を含む場合）、その到達可能性関係は半順序ではなく前順序に対応する.。

アルゴリズム到達可能性を判定するアルゴリズムは、前処理を必要とするものと必要としないものの2種類に大別される。

クエリの数が1件（または少数）である場合、より複雑なデータ構造の使用を避けて直接、所望の頂点ペアの到達可能性を計算する方が効率的なことがある。これは幅優先探索や反復深化深さ優先探索などのアルゴリズムを用いることで線形時間で達成できる.。

多数のクエリを実行する場合は、より洗練された手法が使用できる。手法の正確な選択は、分析するグラフの性質に依存する。前処理時間と若干の追加記憶領域と引き換えに、任意の頂点ペアの到達可能性クエリに最短で時間で答えられるデータ構造を作成できる。以下に、3つの異なる・より専門化された状況に対する3つのアルゴリズムとデータ構造の概要を示す。

ワーシャル–フロイド法

ワーシャル–フロイド法. は任意の有向グラフの推移閉包を計算するために使用でき、上記の定義に示した到達可能性関係を導出する。

このアルゴリズムは最悪の場合の時間との空間を必要とする。このアルゴリズムは到達可能性だけでなく、すべての頂点ペア間の最短経路距離も計算する。負の閉路を含むグラフでは最短経路が未定義になる場合があるが、ペア間の到達可能性は引き続き記録できる。

ソラップのアルゴリズム

平面グラフ状の有向グラフ（有向グラフ）に対しては、が2004年に記述した、はるかに高速な手法が使用できる.。この手法は、の前処理時間をかけてサイズのデータ構造を作成した後、時間で平面グラフ上の到達可能性クエリに答えられる。このアルゴリズムは近似最短経路距離と経路情報も提供できる。

全体的なアプローチは、各頂点に比較的小さな「セパレータパス」の集合を関連付け、頂点から他の任意の頂点への任意のパスがまたはに関連付けられたセパレータの少なくとも1つを通らなければならないようにする。以下に到達可能性に関連する部分の概要を示す。

グラフが与えられると、アルゴリズムはまず任意の頂点から始めて頂点を層に組織化する。層は交互のステップで構築され、最初に前のステップから到達可能なすべての頂点（最初はのみ）を考慮し、次に前のステップへ到達するすべての頂点を考慮することを、すべての頂点が層に割り当てられるまで繰り返す。層の構築により、各頂点は最大2つの層に現れ、内のすべての（ダイパス）は隣接する2つの層とに収まる。を満たす最小のを最後に作成された層とする。

グラフは次に、（はすべての前の層を1頂点に縮約したもの）からなる有向グラフ列として再表現される。すべてのダイパスは最大2つの連続した層に現れ、各は2つの連続した層で形成されるため、内のすべてのダイパスは少なくとも1つのに完全に現れる（2つ以上の連続したには現れない）。

各について、削除するとグラフが元の頂点数の最大を含む3つの成分に分割される3つのセパレータが特定される。は逆向きのダイパスの2層から構築されるため、各セパレータは最大2つのダイパスで構成でき、セパレータ全体で最大6つのダイパスとなる。この集合をとする。そのようなセパレータが常に見つかることの証明は、リプトンとタージャンのに関連しており、これらのセパレータは線形時間で見つけられる。

各について、の有向性によりパスの始点から終点への自然なインデックス付けが可能となる。内の各頂点について、から到達可能な内の最初の頂点と、に到達できる内の最後の頂点を求める。すなわち、からにどれだけ早く入れるか、またのどこまで進んでに戻れるかを調べる。この情報は各に格納される。任意の頂点ペアとについて、がからより早くに接続する場合に限り、はを経由してに到達できる。

を構築する再帰の各ステップについて、各頂点に上記のラベル付けが行われる。この再帰は対数的な深さを持つため、頂点ごとに合計の追加情報が格納される。この時点から、到達可能性の対数時間クエリは、共通する適切なを求めてラベルのペアを見ていくだけで実現できる。元の論文ではさらにクエリ時間をに改善している。

この手法の分析をまとめると、まず層化アプローチにより各頂点が回しか考慮されないよう頂点が分割される。アルゴリズムのセパレータ段階では、グラフが元のグラフの最大のサイズの成分に分割され、対数的な再帰の深さが生まれる。再帰の各レベルでは、セパレータと頂点間の可能な接続を特定するために線形作業のみが必要である。全体の結果として、各頂点にの追加情報のみを格納しての前処理時間が達成される。

亀田のアルゴリズム

thumb|right|200px|亀田の手法に適した有向グラフ（とを追加したもの）

thumb|right|200px|亀田のアルゴリズム実行後の同グラフ（各頂点のDFSラベルを表示）

1975年にT.亀田により提案された、前処理がさらに高速な手法. は、グラフが平面グラフかつ非巡回であり、以下の追加性質も備える場合に使用できる。すなわち、0のすべての頂点と0のすべての頂点が同じ面（通常は外面と仮定）に現れ、その面の境界を入次数0の頂点が一方に、出次数0の頂点が他方に現れるよう（2種類の頂点が交互にならないように）2分割できること。

がこれらの性質を持つ場合、時間だけでグラフを前処理し、頂点ごとにビットの追加情報のみを格納して、任意の頂点ペアの到達可能性クエリに時間で答えられる。

前処理は以下のステップで行われる。まず、入次数0の各頂点に辺を持つ新しい頂点と、出次数0の各頂点から辺を受け取る新しい頂点を追加する。の性質により、これらの追加後も平面性を維持できる（辺の交差が生じない）。各頂点について、グラフの平面的埋め込みに関する順序（例えば時計回り）で隣接リスト（出辺）を格納する。次にカウンタを初期化し、から深さ優先探索を開始する。この探索では、各頂点の隣接リストを必要に応じて左から右へ訪問する。頂点が探索スタックからポップされると値でラベル付けされ、がデクリメントされる。は常に値、は常にでラベル付けされる。次に同じ深さ優先探索を繰り返すが、今度は各頂点の隣接リストを右から左へ訪問する。

完了後、と、およびそれらの接続辺が削除される。残る各頂点はからの値からなる2次元ラベルを格納する。2頂点と、およびそれらのラベルとについて、、、かつ少なくとも1つの成分が厳密に小さい場合に限りと定義する。

この手法の主な結論として、がから到達可能であるのはの場合かつその場合に限り、これは時間で容易に計算できる。

到達可能性

Źródło i licencja