Let \(G=(V,E)\) be a directed graph where \(V\) is the set of vertices and…
2014
Let \(G=(V,E)\) be a directed graph where \(V\) is the set of vertices and \(E\) the set of edges. Then which one of the following graphs has the same strongly connected components as \(G\) ?
- A.
\(G_1 = (V,E_1) \)where\( E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}\) - B.
\(G_2 = (V,E_2)\)where\(E_2 = \left\{(u,v) \mid (v,u) \in E \right\}\) - C.
\(G_3 (V,E_3)\)where\(E_3 = \{(u,v) \mid\)there is a path of length\(\leq2\)from\(u\)to\(v\)in\(E\}\) - D.
\(G_4 = (V_4,E)\)where\(V_4\)is the set of vertices in\(G\)which are not isolated
Attempted by 122 students.
Show answer & explanation
Correct answer: B
Key idea: strongly connected components are defined by mutual reachability (there is a directed path from u to v and from v to u).
If u and v are mutually reachable in G, then there is a path u→…→v and a path v→…→u. Reversing every edge turns those paths into v→…→u and u→…→v, so u and v remain mutually reachable in the graph with all edges reversed.
Conversely, applying the same reversal again returns to the original graph, so mutual reachability in the reversed graph implies mutual reachability in G.
Therefore the graph obtained by reversing every edge (the transpose: G2 where E2 = { (u,v) | (v,u) ∈ E }) has exactly the same strongly connected components as G.