May 22, 2024
May 22, 2024
May 22, 2024
###### Question 176 – ISRO CS 2008
May 22, 2024

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?

Question 92 Explanation:
G(V, E) is a directed graph.

→ It strongly connected.
(A) G1=(V,E1) where E1={(u,v)|(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G2=(V,E2 )where E2={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
This can also be true.
eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G4=(V4,E) where V4 is the set of vertices in G which are not isolated.

If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G4 contain only ‘1’ component, which is not same as G.
G1=(V,E1) where E1={(u,v)|(u,v)∉E}
G2=(V,E2 )where E2={(u,v)│(u,v)∈E}
G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
G4=(V4,E) where V4 is the set of vertices in G which are not isolated