GATE DA 2024 | Question 51

MSQ · 2 marks

Consider the directed acyclic graph (DAG) below:

Directed graph with seven vertices: P and R each have an edge into Q, Q has edges to S and V, S has an edge to U, and V has an edge to T.

Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

  1. Option A: P Q R S T U V
  2. Option B: P R Q V S U T (correct)
  3. Option C: P Q R S V U T
  4. Option D: P R Q S V T U (correct)

Answer

(B), (D)

Explanation

In a topological order every edge points forward, so each vertex comes after all of its predecessors. The edges are \(P \to Q\), \(R \to Q\), \(Q \to S\), \(Q \to V\), \(S \to U\) and \(V \to T\): P and R must precede Q, Q must precede S and V, S must precede U, and V must precede T.

  • A and C fail: both place Q before R, which breaks the edge \(R \to Q\).
  • B holds: after P, R, Q come V, S, U, T, so U follows S and T follows V.
  • D holds: P, R, Q, S, V, T, U also respects every edge.

More than one order is valid because the chains \(S \to U\) and \(V \to T\) do not depend on each other.

Answer: B, D