0

「アルゴリズム入門 3rd」を見ていると、こんな疑問が出てきます。

22.3-13 * 有向グラフ G は、u -> v が、G がすべての頂点 V に対して u から v への単純パスを多くても 1 つ含むことを意味する場合、単連結です。有向グラフが単連結かどうかを判定する効率の良いアルゴリズムを教えてください。

そのような答えのいくつかは、「各頂点からDFSを1回実行します。グラフは、前方エッジがなく、交差エッジがない場合にのみ、単独で接続されます」

しかし、私はこの状況を疑っています。例、グラフのすべてのエッジ (A->D、D-​​>E、E->A、B->C、C->A) の場合、DFS は A で始まるため、C->A は交差エッジですが、Iこのグラフは単結合だと思います。申し訳ありませんが、stackoverflow の許可のため、画像をアップロードできません。

4

1 に答える 1

0

グラフにはクロス エッジがある場合があり、サイクルもある場合があり、グラフは単結合 (SC) になります。前方エッジがある場合、目的地 V への 2 つのパスがあることは明らかですが、この状態で交差エッジがある場合、グラフは SC ではありません:: パスがある場合、ab または zb がグラフ内の交差エッジであると仮定しますa と z の間のグラフは SC ではなく、同じパスがなければ完全に SC です。ab(またはzb)がクロスエッジである場合、aとzの間にパスがあってはなりません。

于 2014-02-21T14:55:23.633 に答える