Question 21

Analyze the given directed acyclic graph (DAG):

• Vertices: $\{a, b, c, d, e, f\}$
• Directed edges: $(a, b), (a, d), (b, c), (d, e), (c, f), (e, f)$

Inspect vertex in-degrees and out-degrees:

• Node $a$ has in-degree 0 and out-degree 2. It must be the very first vertex in every topological ordering.
• Node $f$ has in-degree 2 and out-degree 0. It must be the very last vertex in every topological ordering.

The four middle vertices form two independent parallel directed chains:

• Upper chain: $b \to c$ (vertex $b$ must appear before $c$)
• Lower chain: $d \to e$ (vertex $d$ must appear before $e$)

In any valid topological sort, the sequence must have the form:

where the 4 middle positions are filled with $\{b, c, d, e\}$ such that $b$ precedes $c$ and $d$ precedes $e$.

The number of ways to interleave these two chains is the number of ways to choose 2 positions out of 4 for $b$ and $c$ (with $b$ in the earlier spot and $c$ in the later spot):

The 6 valid topological orderings are:

1. $a, b, c, d, e, f$
2. $a, b, d, c, e, f$
3. $a, b, d, e, c, f$
4. $a, d, b, c, e, f$
5. $a, d, b, e, c, f$
6. $a, d, e, b, c, f$