Multiple choice

Consider the DAG with V = {1, 2, 3, 4, 5, 6}, shown below.

Which of the following is NOT a topological ordering?

  1. 1 2 3 4 5 6

  2. 1 3 2 4 5 6

  3. 1 3 2 4 6 5

  4. 3 2 4 1 6 5
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

We have INDEG (v) = In degree of verter v. As, INDEG (1) = 0, INDEG (2) = 1 INDEG (3) = 1  INDEG (4) = 2 INDEG (5) = 2m            INDEG (6) = 2 Node 1 is with zero indegree, therefore first node in ordering will always 1 thus answer (4) is not a topological ordering.

Keep practicing — related questions