Computer Sciences > Gate 2014 Set-1 > Graph Theory
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
G1 = (V,E1) where E1={(u,v)∣(u,v)∉E}
B
G2 = (V,E2) where E2={(u,v)∣(v,u)∈E}
C
G3 = (V,E3) where E3={(u,v)∣ there is a path of length ≤2 from u to v in E}
D
G4= (V4,E) where V4 is the set of vertices in G which are not isolated

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

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represen...
#14 MCQ
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, a...
#91 MCQ
Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Cons...
#95 MCQ

Related Topics

directed graph strongly connected components SCC properties graph theory GATE Computer Sciences 2014 GATE CS 2014 Set-1 Q6 graph components same SCC as G

Unique Visitor Count

Total Unique Visitors

Loading......