Consider the directed graph below given. Which one of the following is TRUE?
2014
Consider the directed graph below given.
Which one of the following is TRUE?
- A.
The graph does not have any topological ordering.
- B.
Both PQRS and SRQP are topological orderings.
- C.
Both PSRQ and SPRQ are topological orderings.
- D.
PSRQ is the only topological ordering.
Attempted by 146 students.
Show answer & explanation
Correct answer: C
Key constraints: From the graph the directed edges are P→Q, P→R, S→R, S→Q and R→Q. So P and S must come before R and Q, and R must come before Q.
P must appear before R and Q.
S must appear before R and Q.
R must appear before Q.
There is no edge between P and S, so their relative order can be either P then S or S then P.
Conclusion: The only sequences that satisfy all of these constraints place P and S first (in either order), then R, then Q. Therefore the valid topological orderings are
P S R Q
S P R Q
Thus the statement that both PSRQ and SPRQ are topological orderings is correct; the other given statements are false.