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?

G1 = (V, E1) where E1 = {(u, v)|(u, v) ∉ E}

G2 = (V, E2) where E2 = {(u, v)|(v, u) ∈ 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

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? Correct Answer G2 = (V, E2) where E2 = {(u, v)|(v, u) ∈ E}

In a directed graph G Strongly connected will have a path from each vertex to every other vertex.

If the direction of the edges is reverse, then also graph is strongly connected components as G

Option 2: G₂ = (V, E₂) where E₂ = {(u, v)|(v, u) ∈ E}

In this option G₂, edges are reversed and hence it is a strongly connected components as similar to G

So, changing the direction of all the edges, won't change the SCC.

মোঃ আরিফুল ইসলাম

Feb 20, 2025

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?

Related Questions