edited by
11,714 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

7 Answers

Best answer
46 votes
46 votes

Here the answer is B.

A graph is said to be strongly connected if every vertex is reachable from every other vertex.

The strongly connected component is always maximal that is if $x$ is strongly connected component there should not exist another strongly connected component which contains $x$.

If we take $R$ as a strongly connected component but which is part of $PQRS$ and $PQRS$ is part of $PQRSVT$.

edited by
3 votes
3 votes
ans (B)..
2 votes
2 votes
In a strongly connected component every two vertices must be reachable from one to other and it is maximal component.
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.
Answer:

Related questions

6 votes
6 votes
1 answer
4