GATE 2024 DA Q.51: solution and answer

Official answer: B, DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Read the edges from the figure: $P\to Q$, $R\to Q$, $Q\to S$, $Q\to V$, $S\to U$, $V\to T$.

2. A topological order must place the tail of every edge before its head. So: $P$ and $R$ both come before $Q$; $Q$ comes before $S$ and $V$; $S$ comes before $U$; $V$ comes before $T$.

3. (A) P Q R S T U V: $Q$ is at position 2 and $R$ at position 3, so $R\to Q$ is violated. Invalid. (It also puts $T$ before $V$, violating $V\to T$.)

4. (B) P R Q V S U T: $P$ (1) and $R$ (2) come before $Q$ (3); $Q$ comes before $V$ (4) and $S$ (5); $S$ (5) comes before $U$ (6); $V$ (4) comes before $T$ (7). Every edge is respected. Valid.

5. (C) P Q R S V U T: $Q$ is at position 2 and $R$ at position 3, so $R\to Q$ is violated. Invalid.

6. (D) P R Q S V T U: $P$ (1) and $R$ (2) come before $Q$ (3); $Q$ comes before $S$ (4) and $V$ (5); $S$ (4) comes before $U$ (7); $V$ (5) comes before $T$ (6). Every edge is respected. Valid.

7. So the valid topological orderings are (B) and (D).