Consider the directed acyclic graph (DAG) below: Which of the following is/are…
2024
Consider the directed acyclic graph (DAG) below:
Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?
- A.
P Q R S T U V
- B.
P R Q V S U T
- C.
P Q R S V U T
- D.
P R Q S V T U
Attempted by 50 students.
Show answer & explanation
Correct answer: B, D
Key constraints derived from the DAG:
P must come before Q.
R must come before Q.
Q must come before S.
Q must come before V.
S must come before U.
V must come before T.
Check each proposed ordering:
P Q R S T U V — invalid because R appears after Q, which violates the requirement that R come before Q.
P R Q V S U T — valid because P and R appear before Q; Q appears before V and S; V appears before T; and S appears before U.
P Q R S V U T — invalid for the same reason as the first sequence: R appears after Q, violating R before Q.
P R Q S V T U — valid because P and R are before Q; Q is before S and V; S is before U; and V is before T. Any other relative ordering not constrained by edges is allowed.
Conclusion: The valid vertex orderings among the given choices are "P R Q V S U T" and "P R Q S V T U" because they satisfy all directed edges in the DAG.
Note: The question metadata incorrectly marks "P Q R S T U V" as correct; that ordering violates the edge from R to Q and is therefore invalid.