Project ForgeDiscrete Mathematics
Graph Theory
GATE 2014
Hard
Consider the directed graph with edges P→Q, P→R, R→Q, S→R, and S→Q. Which one of the following is TRUE?
- AThe graph does not have any topological ordering.
- BBoth PQRS and SRQP are topological orderings.
- Both PSRQ and SPRQ are topological orderings.
- DPSRQ is the only topological ordering.
Explanation
The graph is a DAG (P→Q, P→R, R→Q, S→R, S→Q), so it does have topological orderings, ruling out A. Checking PSRQ (P,S,R,Q): every edge goes from an earlier letter to a later one (P before Q,R; S before R,Q; R before Q) — valid. Checking SPRQ (S,P,R,Q): S before R,Q; P before Q,R; R before Q — also valid, since S and P have no edge between them so their relative order is free. PQRS fails because it places R after Q, violating R→Q. So both PSRQ and SPRQ work.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.