GATE CS 2016 Set 1 Q11 — Graph Traversals (BFS, DFS)

The given directed graph consists of 5 vertices $\{a, b, c, d, e\}$ with the following directed edges:

• $a \to b$
• $a \to c$
• $b \to d$
• $c \to e$

To find the number of topological orderings, we analyze the dependency constraints:

1. Vertex $a$ has an in-degree of 0 and must always appear first in any topological sort.
2. Once $a$ is placed, we are left with two independent parallel chains: $b \to d$ and $c \to e$.

The remaining 4 positions in the topological ordering must be filled by the elements of these two chains while preserving their internal order ($b$ before $d$, and $c$ before $e$).

The number of ways to choose 2 positions out of the remaining 4 for the chain $b \to d$ is:

Once these 2 positions are chosen, the order of $b$ and $d$ is fixed. The remaining 2 positions must be filled by $c$ and $e$ in their fixed order. Thus, there are exactly 6 different topological orderings.