到達可能性

到達可能性について

概要

到達可能性（とうたつかのうせい）とは、グラフ理論の中で特定の頂点から別の頂点に到達できるかどうかを示す概念です。ある頂点 \( s \) から別の頂点 \( t \) に到達可能であるとは、\( s \) を起点として連続する隣接頂点の列（ウォーク）が存在し、最終的に \( t \) に到達することを意味します。

特に無向グラフの場合、到達可能性はグラフの連結成分を特定することで判断できます。すなわち、二つの頂点が同じ連結成分に属しているとき、互いに到達可能です。この場合、到達可能性は対称的な関係を持ちます。すなわち、\( s \) から \( t \) に到達できる場合は常に、\( t \) から \( s \) にも到達可能です。無向グラフの連結成分は線形時間内で特定できます。しかし、本記事ではより複雑な有向グラフにおける到達可能性の問題に焦点を当てていきます。

定義

有向グラフ \( G=(V, E) \) では、頂点の集合 \( V \) と辺の集合 \( E \) が存在し、ある頂点 \( s \) から \( t \) に到達可能であるとは、\( E \) の推移閉包に従った連続的なパスが存在することを意味します。
筋を追って言えば、\( s \) から始まり、\( t \) で終わる隣接する頂点の列があるという形式です。

有向グラフが非巡回であれば、その到達可能性関係は半順序となります。逆に、任意の半順序は前述の推移的縮減の到達可能性関係として定義できます。このため、\( s \) が \( t \) に到達できるときは、\( t \) が \( s \) に到達不可能なことが推測できます。これは、もし \( s \) から \( t \) に到達し、さらに \( s \) に戻れるとすると、グラフには閉路が存在し、非巡回性が壊れるからです。

アルゴリズム

グラフに対する到達可能性を判定するためのアルゴリズムは、前処理が必要なものとそうでないものに分かれます。クエリが少数の場合は、直接計算する方が効率的ですが、クエリの数が多い場合は、より複雑なデータ構造を用いる必要があります。

ワーシャル–フロイド法

このアルゴリズムは、任意の有向グラフの推移閉包を計算するためのもので、全ての頂点ペア間の到達可能性を評価します。最悪の場合、\( O(|V|^3) \) の時間と \( O(|V|^2) \) のメモリを使用します。

ソラップのアルゴリズム

平面グラフの場合、ミッケル・ソラップによる手法を用いることで、より効率的に\( O(1) \) 時間でのクエリ回答が可能です。この方法では、各頂点にセパレータパスを関連付け、隣接する層を組織します。これにより、ダイパスが特定の層に現れる仕組みが構築されています。

亀田のアルゴリズム

1975年に提案されたこの方法は、グラフが平面かつ非巡回で、特定の条件を満たす際に使用されます。ここでは、通常の探索手法を用い、必要な情報を効率的に記録することにより、\( O(1) \) 時間で到達可能性を求めることができます。

関連する問題

到達可能性に関連する問題として、特定の頂点が障害を起こした際のクエリなどがあります。さらに、他の問題として、グラフの構造が変更された際に迅速に到達可能性を再計算することも重要です。

まとめ

本記事では到達可能性の基本的な概念、定義、アルゴリズム及びその関連性について詳しく解説しました。この理解は、グラフ理論における重要な知見を提供し、さまざまな関連する問題に対処するための基礎となるでしょう。

もう一度検索