演習: 22.5-1 CLRS
新しいエッジが追加された場合、グラフの強連結成分の数はどのように変化しますか?
どこかで与えられた答えは、新しいエッジが追加された場合、次の 2 つのいずれかが発生する可能性があります。
1) 新しい辺が強連結成分に属する 2 つの頂点を連結する場合、強連結成分の数は変わりません。
2) 代わりに、エッジが 2 つの強結合コンポーネントを接続し、エッジが 2 つのコンポーネント間の既存のパスの逆方向にある場合、新しい強結合コンポーネントが作成され、コンポーネントの数が増加します。
2番目の点は間違っていると思います。
2 つの強く接続されたコンポーネントC とC'
があるとし
ます その後、何も起こりません。
b) エッジ C->C' がそれらの間に存在し、新しいエッジがC'->Cとして接続 する場合、C' は C にマージされ、すべての頂点が互いに到達可能になるため、強く接続されたコンポーネントの数が 1 減少します。
私が間違っている場合は修正してください。