0

有向グラフがあると仮定します。これは完全なグラフではなく、複数の SCC があります。グラフを転置してコサラジュのアルゴリズムを使うと強連結成分のパターンが変わるのかな？「グラフを転置する」とは、エッジの方向を反転することを意味します。元のグラフではなく転置/反転グラフで SCC を見つけようとすると、見つけた SCC は異なるでしょうか?

SCCのアルゴリズムを誤解し、転置/反転グラフで実行したため、この質問を思いつきました。私が得たのは正解と同一のSCCです/コサラジュのアルゴリズムを実行します。それはすべてのグラフに普遍的に当てはまりますか?

4

2 に答える 2

1

http://en.wikipedia.org/wiki/Kosaraju%27s_algorithmを見ると、次のことがわかります。

「転置グラフ (すべてのエッジの方向が逆になっている同じグラフ) には、元のグラフとまったく同じ強連結成分があります。」

(強く接続されたコンポーネントは、コンポーネント内のすべての頂点から他のすべての頂点に到達できるコンポーネントであり、すべてのリンクを逆にしても保持されます)。もちろん、異なるコンポーネントを接続するリンクは逆になりますので、異なる順序でコンポーネントが出てくることを期待しています。

于 2013-11-20T05:47:36.103 に答える