Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and…

GATE · 2014 · CS · Set 1 · Computer Science & IT

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.
$G_1 = (V,E_1)$ where $E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}$
B.
$G_2 = (V,E_2)$ where $E_2 = \left\{(u,v) \mid (v,u) \in E \right\}$
C.
$G_3=(V,E_3)$ where $E_3=\{(u,v)\mid \text{there is a path of length }\leq 2\text{ from }u\text{ to }v\text{ in }E\}$
D.
$G_4 = (V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated

Attempted by 215 students.

Explore the full course: Gate Guidance By Sanchit Sir

Let \(G=(V,E)\) be a directed graph where \(V\) is the set of vertices and…