GATE 2016 CS – Question 21
Consider the following directed graph:
[Directed graph on vertices a, b, c, d, e, f with edges a→b, b→c, c→f, a→d, d→e, e→f.]
The number of different topological orderings of the vertices of the graph is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
The graph has two chains between $a$ and $f$: $b \to c$ and $d \to e$. A topological order starts with $a$ and ends with $f$, and in between it merges the two chains while keeping each chain's own order. The number of ways to interleave two chains of 2 items is $\binom{4}{2} = 6$.