15

任意のグラフの 2 つの頂点間のすべての単純なパスを列挙するには、一般に指数関数的な時間がかかります。これは、頂点間に指数関数的な数の単純なパスが存在する可能性があるためです。しかし、2 つの端点の間の少なくとも 1 つの単純なパス上にある頂点だけに関心がある場合はどうなるでしょうか。

つまり:無向グラフと 2 つの異なる頂点が与えられた場合、2 つの頂点間の少なくとも 1 つの単純なパス上にあるすべての頂点を見つける多項式時間アルゴリズムはありますか? これは接続性とは異なります。行き止まりと行き止まりは除外されます。ただし、パスの分岐と合流は許可されます。

この問題を解決するように見えるアルゴリズムを作成するのは非常に簡単ですが、場合によっては失敗するか、異常なケースでは指数関数的な実行時間がかかります。

より一般的に:グラフ内の頂点の 2 つの互いに素なセットが与えられた場合、一方のセットの頂点からもう一方のセットの頂点への単純なパス上にあるすべての頂点を見つける多項式時間アルゴリズムはありますか?

（これに対する本当に明白な解決策がある場合は、私を許してください。確かにあるべきだと感じています。）

4

2 に答える 2

17

これは、線形時間の決定論的ソリューションです。2 つの端点 (a と b と呼びましょう) の間にエッジを挿入すると、そのようなエッジがまだ存在しない場合、問題は、a とb. このようなセットは、ノード (二重接続コンポーネントとも呼ばれます) を削除しても切り離すことができない a と b を含む最大サブグラフに対応することを確信できます。このページでは、ホップクロフトとタージャンの概念と古典的な線形時間 (DFS ベース) アルゴリズムについて説明し、すべての二重接続されたコンポーネントを識別します (必要なのは、a と b を含むものだけです)。

2 つのセット間の単純なパス (それらを A と B と呼びましょう) に関する 2 番目の質問は、A のすべての頂点へのエッジを持つ新しい頂点 a と、B のすべての頂点へのエッジを持つ頂点 b を作成することで、最初の質問に減らすことができます。次に、a と b の最初の質問を解きます。

于 2012-05-31T05:55:40.063 に答える
1

確率的な解決策を気にしますか？つまり、すべての頂点を見つけることを保証するものではありませんが、通常は最初に試行し、2 ～ 3 回試行すると圧倒的に見つかる可能性が高くなります。

それでよろしければ、すべてのエッジにランダムに抵抗を割り当て、ソースを電圧 1 に、シンクを電圧 0 にすると、すべてのノードの電圧を解きます。異なる電圧にあるのは明らかに単純なパスです (パスは簡単に作成できます。一方の端から電圧が上昇し、もう一方の端から電圧が下降するだけです)。それを接続する 2 つのノードが同じ電圧にあるエッジは、理論的には発生する可能性がありますが、単純なパス上にある可能性は非常に低いです。

ランダムに割り当てられた抵抗のセットをいくつか繰り返して、単純なパス上にあるすべてのエッジを見つける可能性が圧倒的に高くなります。(この答えはまだ証明されていませんが、間違っている可能性はほとんどありません。)

もちろん、単純なパス上にあるすべてのエッジがわかれば、単純なパス上にあるすべての頂点を取得するのは簡単です。

アップデート

私は次のことが正しいと信じていますが、証拠はありません。一連の抵抗を取り、電圧を計算するとします。単純なパスにあるすべてのエッジには、別のエッジ (おそらく同じ) があり、そのエッジのみの抵抗を変化させると、最初のエッジの両端の電圧が変化します。もしそうなら、多項式時間で単純なパスのすべてのエッジを識別することが可能です。

直感的には理にかなっていますが、それを証明する方法がわかりません。

于 2012-05-31T01:32:50.657 に答える