Register

GATE IT 2006 | Question: 46

• edited by
19,615 views
50 50 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 \}$ 

6 Answers

Best answer
59 59 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 3 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.
2 2 votes

A Strongly Connected Component (SCC) in a directed graph is a group of nodes where:

# Every node is reachable from every other node in the same group.

# Think of it like a mutually-following friend group on social media.

 

Easy rule to spot Strongly Connected Components (in small graphs):

  1. 1. If there's a cycle, all nodes in the cycle form an SCC.
  2. 2. Isolated nodes or one-direction chains (like 5 → 6 → 7) are not strongly connected unless you can go back.
So, the answer would be {P, Q, R, S, T, V} {U}
0 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}
–1 –1 vote

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)

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2006 | Quest...Next → · GATE IT 2006 | Quest...
← Previous in category · GATE IT 2006 | Quest...Next in category → · GATE IT 2006 | Quest...
Position:
Show:

Related questions

42 42 votes
8 answers 8 answers
23.3k
23.3k views
Kathleen asked Sep 11, 2014
23,304 views
GATE CSE 2008 | Question: 7
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$$\Theta(m)$...
43 43 votes
9 answers 9 answers
20.7k
20.7k views
Ishrat Jahan asked Oct 31, 2014
20,660 views
GATE IT 2006 | Question: 47
Consider the depth-first-search of an undirected graph with $3$ vertices $P$, $Q$, and $R$. Let discovery time $d(u)$ represent the time instant when the vertex $u$ is fi...
102 102 votes
6 answers 6 answers
31.1k
31.1k views
gatecse asked Feb 14, 2018
31,128 views
GATE CSE 2018 | Question: 43
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and ...