Register

GATE CSE 2014 Set 1 | Question: 13

• retagged by
7,714 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
User Avatar

5 Answers

0 votes
0 votes
Think of edges as courses. If an edge is there between two courses as C1->C2, then C1 is prerequisite for C2.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

21 votes
21 votes
7 answers
1
pC asked Dec 21, 2015
7,938 views
GATE CSE 2007 | Question: 5
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$ $6$ $5$ $3$ $2$ $4$ $1$ $6$ $5$
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$...
User Avatar
34 votes
34 votes
4 answers
2
go_editor asked Sep 26, 2014
12,219 views
GATE CSE 2014 Set 1 | Question: 11
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjacency matrix? $\Theta(n)$ $\Theta(n+m)$ $\Theta(n^2)$ $\Theta(m^2)$
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$, when $G$ is represented as an adjac...
User Avatar
61 votes
61 votes
5 answers
4
Sandeep Singh asked Feb 12, 2016
28,611 views
GATE CSE 2016 Set 1 | Question: 11
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.
User Avatar
Link Copied!