For the given DAG, which of the following is NOT a topological ordering?
2021
For the given DAG, which of the following is NOT a topological ordering?
Answer: D. CBDAFE — ConceptA topological ordering of a directed acyclic graph places every vertex before every vertex reached by one of its outgoing edges. Equivalently, for each…
- A.
ABCDEF
- B.
ACBDEF
- C.
ACBDFE
- D.
CBDAFE
Attempted by 273 students.
Show answer & explanation
Correct answer: D
Concept
A topological ordering of a directed acyclic graph places every vertex before every vertex reached by one of its outgoing edges.
Equivalently, for each directed edge u → v, u must occur before v in the sequence.
Application
Read the DAG constraints: A precedes B and C; B precedes D and E; C precedes D and F; and D precedes E and F.
In CBDAFE, C and B occur before A. This contradicts the edges A → C and A → B, which require A to occur before both vertices.
Therefore, CBDAFE is not a topological ordering of the given DAG.
Cross-check
Each of ABCDEF, ACBDEF, and ACBDFE places A before B and C, both B and C before D, and D before E and F. Thus, each of those sequences satisfies every directed-edge constraint.
Result
The ordering that is not topological is CBDAFE.