GATE Overflow Test Series | Algorithms | Test 2 | Question: 16

Question

Consider the following directed graph.


The number of different topological orderings of the vertices of the graph is $\_\_\_\_\_\_\_\_.$

Answer 1

In the topological ordering $b-c-d$ and $e-f-g$ must be in order but both sets of $3$ elements can be permuted in any order. That is, we have $6$ elements to be permuted where $3$ each must be in a given order. So, number of possible permutations $ = \dfrac{6!}{3!3!} = 20.$

Comments

Can you please elaborate, its’ not quite clear to me

---

Refer it

https://gateoverflow.in/39669/Gate-cse-2016-set-1-question-11

Answer 2

 Answer is $_{3}^{6}\textrm{C}$ = $6!/3!*3!$

Reason : 

we can say 1 thing for sure : a _ _ _ _ _ _ f is the layout

Now, we have 6 elements and 6 places.

But b – c – d and e – f – g order is fix.

So, we just have to chose 3 places from 6 for b -c – d : $6C3$ & then we can place e,f,g in remaining places in their respective order.