algorithm - 弱連結グラフ？

Question

ウィキペディアのページから：

「有向グラフは、すべての有向辺を無向辺に置き換えると連結 (無向) グラフが生成される場合、弱連結と呼ばれます」

これは正確ですか？

上のグラフは、すべての有向辺が無向辺に置き換えられたときに接続されます。しかし、弱い型付けのプロパティに違反する B から D または D から B の間にパスはありません。

Answer 1

はい、それはほとんどの場所で使用されていると思われる定義です。いくつかのグラフ検索ドキュメントからの別の言い回し、

弱連結成分は、エッジ方向に違反することによって相互に到達可能なノードの最大グループです。

Answer 2

ウィキペディアの有向グラフのページによると：

有向グラフ G は、G のすべての有向エッジを無向エッジで置き換えることによって得られる無向下層グラフが連結グラフである場合、弱連結 (または単に連結 [4]) と呼ばれます。u から v への有向パスと、頂点 u,v のすべてのペアについて v から u への有向パスが含まれている場合、有向グラフは強連結または強です。強いコンポーネントは、最大の強く接続されたサブグラフです。

したがって、はい - 定義は正しいです。グラフが強く接続されている場合と弱い接続の場合があることに注意してください。