Register

GATE IT 2006 | Question: 46

• edited by
11,906 views
37 votes
37 votes

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

  1. $\left \{ P, Q, R, S \right \}, \left \{  T \right \},\left \{  U \right \}, \left \{  V \right \}$
  2. $\left \{ P,Q, R, S, T, V \right \}, \left \{  U  \right \}$ 
  3. $\left \{ P, Q, S, T, V \right \}, \left \{  R \right \},\left \{  U \right \}$ 
  4. $\left \{ P, Q, R, S, T, U, V \right \}$ 
• edited by
User Avatar

7 Answers

0 votes
0 votes
1)A strongly connected component of a directed graph G=(V, E) is a maximal set of vertices such that any 2 vertices in the set are strongly connected(mutually reachable).

2)In a directed graph G=(V, E) two nodes u and v are strongly connected if and only if they are mutually reachable

i.e. there is a path from u to v and a path from v to u.

based on the above definitions we can split the vertices of the given graph into 2 sets They are

{P, Q, R, S,T, V},{U}
User Avatar
–1 votes
–1 votes

A graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time.

In a Strongly Connected component Every two vertices must be reachable from one to other and it is maximal component,

From the above option {P, Q, S, T, V}, {R}, {U} 

Option - (c)

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

6 votes
6 votes
1 answer
8
Ishrat Jahan asked Oct 31, 2014
6,089 views
GATE IT 2006 | Question: 10
A problem in NP is NP-complete if it can be reduced to the 3-SAT problem in polynomial time the 3-SAT problem can be reduced to it in polynomial time it can be reduced to any other problem in NP in polynomial time some problem in NP can be reduced to it in polynomial time
A problem in NP is NP-complete ifit can be reduced to the 3-SAT problem in polynomial timethe 3-SAT problem can be reduced to it in polynomial timeit can be reduced to an...
User Avatar
Link Copied!