Dark Mode

9,093 views

36 votes

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

- $\left \{ P, Q, R, S \right \}, \left \{ T \right \},\left \{ U \right \}, \left \{ V \right \}$
- $\left \{ P,Q, R, S, T, V \right \}, \left \{ U \right \}$
- $\left \{ P, Q, S, T, V \right \}, \left \{ R \right \},\left \{ U \right \}$
- $\left \{ P, Q, R, S, T, U, V \right \}$

8

44 votes

Best answer

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

3 votes

That is ok.

But why do we need it here? It takes lots of time. So, I think with the definition of strongly connected component, we can say B) is answer. isn't it?

See the definition of strongly connected component. It tells , if we go from one vertex of the graph to all other vertex then the graph is strongly connected. Now chk here, only option B) match. Isn't it?

2