8

頂点のセットが強く連結されたコンポーネントの一部である場合、コンポーネント内のすべての頂点が互いに到達できることを理解しています。サイクル。

ここで、この事実を使用して、グラフG =（V、E）にサイクルがある場合、そのサイクルはscc内にある必要があると主張したいと思います。

言い換えれば、すべてのサイクルはsccの一部でなければなりません（私の主張）。

私の主張に対する反例は思いつかないので、グラフにsccの一部ではないサイクルがあるかどうかを知りたいと思います。
または私の主張は正しいですか？

4

2 に答える 2

11

あたりです。頂点のセットがサイクル内にある場合、それらはすべて（サイクルを一周することによって）互いに到達可能であるため、定義上、それらはSCCです。

そうは言っても、それはプログラミングの問題ではありません:)

于 2012-10-18T17:08:08.240 に答える
2

e =（u、v）を問題のエッジとします。これは、uがG {e}のvに接続されている場合にのみ、eを含むGのサイクルであることに注意してください。私たちのアルゴリズムは、G {e}でuからDFSを実行するだけで、vがuから到達可能である場合はyesを出力し、それ以外の場合はnoを出力します。このアルゴリズムは線形時間で実行され、DFSは線形時間で実行されます（そして、uを含むコンポーネントを見つけるDFSアルゴリズムの一部のみを実行します）。このアルゴリズムは明らかに正しいです。uが何らかのパスpによってG{e}のvに接続されている場合、エッジeをpに追加してサイクルを形成できます。それ以外の場合、Gからeを削除すると、uとvが切断されます。

于 2012-10-22T09:41:40.503 に答える