Correct : a
Definition of Strongly Connected Component:
A strongly connected component (SCC) of a directed graph is a maximal set of vertices such that every vertex is reachable from every other vertex in the set.
Option A: G1 is the complement of G.
The edges of G are removed and new edges are introduced, which can change the reachability between vertices. Therefore, the SCCs may change.
Option B: G2 is the transpose of G, where every edge (u,v) in G becomes (v,u).
If there is a path from u to v in G, reversing all its edges gives a path from v to u in G2. Thus, if u and v are mutually reachable in G, they are also mutually reachable in G2, and vice versa.
Therefore, G and its transpose have exactly the same SCCs.
Option C: G3 adds edges for paths of length 2. Adding such shortcut edges does not change reachability, because every new edge already corresponds to a path in G. Hence, C also preserves the SCCs.
Option D: G4 removes isolated vertices. An isolated vertex itself forms an SCC, so removing it changes the set of SCCs.
Conclusion:
The standard and intended answer is:
Answer: (B) G2 = (V,E2) where E2 = {(u,v) | (v,u) ∈ E}
Similar Questions
Total Unique Visitors