Question 23

The graph has vertices $\{P, Q, R, S\}$ and directed edges:

• From $P$: $P \to Q$, $P \to R$
• From $S$: $S \to Q$, $S \to R$
• From $R$: $R \to Q$

In-degrees of vertices:

• $P$: 0 (no incoming edges)
• $S$: 0 (no incoming edges)
• $R$: 2 (incoming from $P$ and $S$)
• $Q$: 3 (incoming from $P, S$, and $R$)

A topological ordering must place every vertex before all vertices it has edges to.

• Either $P$ or $S$ can be chosen as the first vertex.
• If $P$ is chosen first, remaining vertices have in-degrees: $S: 0, R: 1, Q: 2$. Thus $S$ must be second.
  After choosing $S$, in-degrees become: $R: 0, Q: 1$. Thus $R$ must be third, followed by $Q$.
  This yields the sequence: $P, S, R, Q$.
• If $S$ is chosen first, remaining vertices have in-degrees: $P: 0, R: 1, Q: 2$. Thus $P$ must be second.
  After choosing $P$, $R$ is third, followed by $Q$.
  This yields the sequence: $S, P, R, Q$.

Both PSRQ and SPRQ are valid topological orderings, matching option C.