最後の仮定は当てはまりません。たとえば、グラフを見てくださいG = (V,E)
。ここでE = {(v_i,v_j) | i < j }
、グラフは明らかに DAG です。したがって、最大の強連結成分を見つけてもグラフは変わりません。また、グラフにはハミルトニアンパスがありますが、d_out(v_1) > 1
[仮定|V| > 3
]。
しかし、あなたは正しい道を進んでいます。
高レベルの疑似コードのアルゴリズム:
- グラフ内の極大強連結成分を見つけます。結果のグラフは DAG です。
- 結果のグラフでトポロジカル ソートを使用します1。
- 順序付けされた並べ替えがハミルトニアン パスを作成するかどうかを確認する
- そうであれば - true を返し、そうでなければ false を返します
請求:
グラフの MSCC を表す DAG にハミルトニアン パスがある場合にのみ、すべての頂点を持つパスが存在します。
主張の証明:
<-
ハミルトニアン パスが存在する場合 - そのようなパスは MSCC ごとに自明です - パスはすべての頂点を通過し、ハミルトニアン パスで選択されたエッジを表すアウト エッジに到達しますMSCCグラフで。
→
そのようなパスが存在する場合は、そうしますv0->v1->...vm
。
が横たわる
最大の強連結成分を
示しましょう。ここで、元のグラフのパスについては、MSCC グラフ2のパスもあります。
上記のパスで ifが 2 回 [またはそれ以上] 出現することに注意してください - 2 つの出現は互いに隣接しています。V_i
v_i
v0->v1->...->vm
V_0->V_1->...->V_m
V_i
V_i->V_k->...->V_i
実行可能なパスです - V_i と V_k は最大ではありません。これは、それらを 1 つのより大きな SCC に結合できるためです。
ここで、それぞれV_i
がそのすべての出現を 1 つに折りたたむと、パスが得られます-それぞれV_i
が最大 1 回出現する場所 [理由を示した]、および 1 つだけ [すべてv_i
が元のパス上にあり、MSCC を完全に削除しなかったため] -それらを折りたたんだだけです]。
したがって、生成されたパスは、MSCC グラフのハミルトニアン パスです。
提案されたアルゴリズムの正しさの証明:
元のグラフに要求されたパスが存在する場合にのみ、MSCC グラフにハミルトニアン パスが存在することを示したので、
->
アルゴリズムは true を返しました -> アルゴリズムは DAG でハミルトニアン パスを見つけました-> Dag にはハミルトニアン パスがあります [脚注 1] -> 元のグラフで要求されたパスがあります。
<-
アルゴリズムは false を返しました -> アルゴリズムは DAG にハミルトニアン pat を見つけませんでした -> DAG にハミルトニアン パスはありません [脚注 1] -> 元のパスに要求されたパスはありません。
QED
1: DAG では、ハミルトニアン パスが存在する場合は一意のトポロジカル ソートがあり、ハミルトニアン パスが存在する場合は、トポロジカル ソートの頂点の順序です。したがって、DAG では、ハミルトニアン パスを見つけるのは簡単です。
2: 実際には、これは少し修正されたものであり、実際V_i->V_i
には MSCC グラフのエッジではありませんが、ここではそれを 1 つとして示しましょう。