Consider directed acyclic graph with vertices Which of the following
Consider a directed acyclic graph with vertices v1,v2,v3,v4,v5,v6
Which of the following is not a topological order?
- A.
v1, v3, v2, v4, v5, v6
- B.
v1, v3, v2, v4, v6, v5
- C.
v1, v2, v3, v4, v5, v6
- D.
v3, v2, v4, v1, v6, v5
Attempted by 16 students.
Show answer & explanation
Correct answer: D
Topological order: A topological order is a linear ordering of vertices where for every directed edge u -> v, u appears before v.
Directed edges in the graph:
v1 -> v2
v1 -> v3
v2 -> v4
v2 -> v5
v3 -> v4
v3 -> v6
v4 -> v5
v4 -> v6
Test the sequence v3, v2, v4, v1, v6, v5:
Edge v1 -> v2 is violated because v1 appears after v2 in the sequence.
Edge v1 -> v3 is violated because v1 appears after v3 in the sequence.
Because these predecessor-successor relationships are not respected, the sequence v3, v2, v4, v1, v6, v5 is not a topological order.
The other provided sequences are valid topological orders because they place each predecessor before its successors. For example:
v1, v3, v2, v4, v5, v6 — v1 comes before v2 and v3; v2 before v4 and v5; v3 before v4 and v6; v4 before v5 and v6.
v1, v3, v2, v4, v6, v5 — same predecessor-before-successor checks hold.
v1, v2, v3, v4, v5, v6 — obvious linear ordering that respects all edges.