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

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

1. A.

   \(G_1 = (V,E_1) \) where \( E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}\)

2. B.

   \(G_2 = (V,E_2)\) where \(E_2 = \left\{(u,v) \mid (v,u) \in E \right\}\)

3. 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\}\)

4. D.

   \(G_4 = (V_4,E)\) where \(V_4\)  is the set of vertices in \(G\) which are not isolated

Attempted by 210 students.

The worked solution is available to enrolled students.