The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
2.9k views

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
asked in DS by Veteran (103k points)
recategorized by | 2.9k views
+3
Both B & C seem true.
0

Both Gate official key & answers here say "B" is the answer than why "C" is mentioned as answer down in this page.

0
Updated ..that was a typo
0
What is strongly connected component?

2 Answers

+38 votes
Best answer

(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 $<= 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.

answered by Veteran (359k points)
edited by
0
they said if there is path <=2 then uv will be edge in v, e3 graph ...rt
0
Yes but you tell me where is the path from D to C in original graph??
+2
i got it thanks
0

For option C, path of len<=2 i.e. path of len zero is also to be considered.

Say A-B-C is one SCC component and D(isolated vertex) is another SCC. So in G there are two SCC.

But in G3{ V,E3 }, this vertex D will be connected with bidirectional edges to all A , B, C reducing no. of SCC by 1.

New Doc 2017-10-22.jpg

0
@abishek

yes , i think this one proves C also wrong
0
@arjun sir

When the original graph has a strongly connected component which includes isolated vertex

then option C fails

because length <=2 and therefore also includes path length =0 and will give rise to a path which is not there in the original, thereby changing the number of strongly connected components
+1

@A_i_$_h : If the oath do not exist then path length would be undefined/infinity. If we take zero then shortest path wont work.

Remember ,if we apply dijkstra/bellman ford on graph and it has isolated vertex,then path would be not defined.If you define it as zero then it would report 0 length path,which is wrong

0
@rahul

yea valid one :)
0

@From cormen

0

@Arjun Sir
Pls check: If there is a path of length ≤ 1 from u to v in E, still the SCC will be same as in G right?

–3 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.
answered by Active (1.2k points)
+7
Your counter example for (B) is not correct. When we reverse the direction of all edges, it again forms a cycle rt- in reverse direction?
0
doubt: (D) also seems correct.. V4 is set of of vertices which in G which are not isolated. Anyways those isolated vertices makes no contribution in strongly connected component.. so even if we choose  those or not the graph gonna  have the same connected component as that of G... Isn't it..??

So (B) and (D) both seems correct..??
+1
As per official answer GATE 2014 answer key it is B. Also counter example for B is incorrect.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,053 questions
47,651 answers
147,212 comments
62,380 users