recategorized by
16,714 views
55 votes
55 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$ ?

  1. $G_1$ = $(V,E_1)$ where $E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}$
  2. $G_2$ = $(V,E_2)$ where $E_2 = \left\{(u,v) \mid (v,u) \in E \right\}$
  3. $G_3$ = $(V,E_3)$ where $E_3 = \{(u,v) \mid$ there is a path of length $\leq2$ from $u$ to $v$ in $E\}$
  4. $G_4$ = $(V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated
recategorized by

3 Answers

Best answer
78 votes
78 votes

(A) is false. Consider just two vertices connected to each other. So, we have one SCC. The new graph won't have any edges and so $2$ SCC.

(B) is true. In a directed graph an SCC will have a path from each vertex to every other vertex. So, changing the direction of all the edges, won't change the SCC.

(D) is false. Consider any graph with isolated vertices- we loose those components.

(C) is a bit tricky. Any edge is a path of length $1$. So, the new graph will have all the edges from old one. Also, we are adding new edges $(u,v)$. So, does this modify any SCC? No, because we add an edge $(u,v)$, only if there is already a path of length $\leq 2$ from $u$ to $v$- so we do not create a new path.  So, both (B) and (C) must answer, though GATE key says only B.

edited by
6 votes
6 votes

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)│(v,u)∈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.

reshown by
–2 votes
–2 votes
A. Can be eliminated as if the component is strongly connected in E then it will not be strongly connected in E's complement.

B.This is reversing the directions of the edges. When a triangle is considered for instance, where the directions are such that it will form a cycle, on reversing these directions the triangle will no more be strongly connected as there will be a vertex from which we cant reach out to any other vertex.

C.This is mostly the answer as according to the condition the number of edges in E3 will be those present in E and also additional edges which connect all U to all V such that UV<=2. Hence the connected component will stay connected.

D.V4 has only single vertices ,i.e those which were isolated in G and no edges will be present between them.
Answer:

Related questions

90 votes
90 votes
11 answers
2
go_editor asked Sep 26, 2014
24,259 views
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is...
100 votes
100 votes
10 answers
4