3

有向グラフである G が与えられた場合、G のすべての頂点を通るパス (単純なパスである必要はありません) はありますか?

最初に、非巡回グラフと強連結グラフで何が起こるかを調べる必要があります。次に、強連結成分のグラフを使用して、一般的なグラフの解を見つける必要があります。

これまでのところ、強く接続されたグラフには常にパスがあることがわかりました。非巡回グラフの場合、ソースが複数ある場合、パスは存在しません。また、D out が 1 より大きい頂点が存在する場合、パスは存在しません。

問題は、最後のものが正しいかどうか確信が持てず、間違っている場合、私のアルゴリズムが間違っていることです。

4

1 に答える 1

1

最後の仮定は当てはまりません。たとえば、グラフを見てくださいG = (V,E)。ここでE = {(v_i,v_j) | i < j }、グラフは明らかに DAG です。したがって、最大の強連結成分を見つけてもグラフは変わりません。また、グラフにはハミルトニアンパスがありますが、d_out(v_1) > 1[仮定|V| > 3]。

しかし、あなたは正しい道を進んでいます。

高レベルの疑似コードのアルゴリズム:

  1. グラフ内の極大強連結成分を見つけます。結果のグラフは DAG です。
  2. 結果のグラフでトポロジカル ソートを使用します1。
  3. 順序付けされた並べ替えがハミルトニアン パスを作成するかどうかを確認する
  4. そうであれば - true を返し、そうでなければ false を返します

請求：

グラフの MSCC を表す DAG にハミルトニアン パスがある場合にのみ、すべての頂点を持つパスが存在します。

主張の証明:
<-
ハミルトニアン パスが存在する場合 - そのようなパスは MSCC ごとに自明です - パスはすべての頂点を通過し、ハミルトニアン パスで選択されたエッジを表すアウト エッジに到達しますMSCCグラフで。
→
そのようなパスが存在する場合は、そうしますv0->v1->...vm。 が横たわる 最大の強連結成分を
示しましょう。ここで、元のグラフのパスについては、MSCC グラフ2のパスもあります。 上記のパスで ifが 2 回 [またはそれ以上] 出現することに注意してください - 2 つの出現は互いに隣接しています。V_iv_i
v0->v1->...->vmV_0->V_1->...->V_m
V_iV_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 つとして示しましょう。

于 2012-04-17T07:21:40.190 に答える