Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of…
20072022
Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?
- A.
1 2 3 4 5 6
- B.
1 3 2 4 5 6
- C.
1 3 2 4 6 5
- D.
3 2 4 1 6 5
Attempted by 150 students.
Show answer & explanation
Correct answer: D
Constraints: The directed edges (precedence relations) in the graph are: 1 → 2, 1 → 3, 2 → 4, 2 → 5, 3 → 4, 3 → 6, 4 → 5, 4 → 6.
Check each given sequence:
1 2 3 4 5 6 — Valid. Every edge is respected: 1 before 2 and 3; 2 before 4 and 5; 3 before 4 and 6; 4 before 5 and 6.
1 3 2 4 5 6 — Valid. Node 1 comes before both 3 and 2; the rest of the precedence relations remain satisfied.
1 3 2 4 6 5 — Valid. Although 6 appears before 5, there is no edge requiring 5 before 6. All directed edges (including 2 → 5 and 4 → 5 and 4 → 6) are still respected.
3 2 4 1 6 5 — Not valid. Node 1 appears after nodes 3 and 2, which violates the edges 1 → 3 and 1 → 2. Because those prerequisites are not met, this sequence is not a topological ordering.
Answer: The sequence "3 2 4 1 6 5" is NOT a topological ordering because it violates edges from node 1 to nodes 2 and 3.