The Gateway to Computer Science Excellence

0 votes

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 ish 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

Can anyone give a detailed answer to this question, please? :)

( 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 ish 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

Can anyone give a detailed answer to this question, please? :)

closed as a duplicate of:
GATE2014-1-3

52,218 questions

59,890 answers

201,084 comments

118,128 users