retagged by
7,604 views
31 votes
31 votes

Consider the directed graph below given. 

Which one of the following is TRUE?

  1. The graph does not have any topological ordering.
  2. Both PQRS and SRQP are topological orderings.
  3. Both PSRQ and SPRQ are topological orderings.
  4. PSRQ is the only topological ordering.
retagged by

5 Answers

Best answer
33 votes
33 votes

C. Both PSRQ and SPRQ are topological orderings

  1. Apply DFS by choosing P or S as starting vertices
  2. As the vertex gets a finishing time assign it to the head of a linked list
  3. The linked list is your required topological ordering
edited by
33 votes
33 votes

choose vertex in the graph which has 0 indegree . now see graph has such two vertices ie P,S so we can start topological sort either from vertex P or from S .

lets first start from vertex P now remove this vertex from graph ,we left with three vertices named asQ,S,R from these vertices see which vertex has INDEGREE 0,S vertex HAS indegree 0 therefore sequence is P,S,R,Q

repeat the above step from vertex S we get sequence as S,P,R,Q

edited by
7 votes
7 votes
The graph doesn't contain any cycle, so there exist topological ordering. P and S must appear before R and Q because there are edges from P to R and Q, and from S to R and Q.

answer is c
0 votes
0 votes

 


There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.

Answer:

Related questions

21 votes
21 votes
7 answers
1
pC asked Dec 21, 2015
7,768 views
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...
61 votes
61 votes
5 answers
2
Sandeep Singh asked Feb 12, 2016
28,243 views
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.
19 votes
19 votes
4 answers
4
go_editor asked Sep 28, 2014
5,155 views
The function $f(x) =x \sin x$ satisfies the following equation: $$f''(x) + f(x) +t \cos x = 0$$The value of $t$ is______.