Project ForgeConsider a DAG with V={1,2,3,4,5,6} and edges 1→2, 1→3, 2→4, 2→5, 3→4, 3→6, 4→5, 4→6 (arranged so that 2,5 form a top row, 1,4 a middle row, and 3,6 a bottom row, with 1 pointing to 2 and 3, and 2,3 both pointing into 4, and 4 in turn pointing to 5 and 6 alongside 2's direct edge to 5 and 3's direct edge to 6). Which of the following is NOT a topological ordering?
- A1 2 3 4 5 6
- B1 3 2 4 5 6
- C1 3 2 4 6 5
- 3 2 4 1 6 5
Explanation
The edge 1→2 requires 1 to appear before 2 in any valid topological ordering. In option (D) '3 2 4 1 6 5', vertex 2 appears at position 2 while vertex 1 appears at position 4 — 1 comes AFTER 2, violating the edge 1→2. Options (A),(B),(C) all satisfy every edge constraint (1 before 2,3; 2,3 before 4; 4 before 5,6; 2 before 5; 3 before 6).
Source: GATE CS 2007 (2007)
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.