ME Test Series

Question

The number of totally ordered sets compatible to the given POSET are ________

Comments

4.. not sure about it

---

A total order set is a chain in every two elements are comparable. Here 4 chains are there

---

40

---

@Priyanka Agarwal please explain

---

Toset compatible with poset means find no of topological sort possible

---

Priyanka Agarwal little ellaborate plss

---

I think 4, answer given by made easy is wrong

---

mehul vaidya

Question is noting but find the number of topological ordering.

$2 * \frac{6!}{3! * 3!} = 40$

---

can you please explain how you found above equation ,.

a c b d e g i k can be topological order but not TOS

because for TOS every element must be comparable to every other element in TOS , but here c and b and not comparable

Please reply

---

@kumar.dilip so how are the dependencies preserved (e->g), (g->i), (f->h), (h->j), if we place this six letters in 6C3 ways???

---

Here we have 11 nodes hence 11 positions. To satisfy topological ordering we have to fix node a at first position, node k at 11th position, and node d at 4th position. 

Now we have 2,3,5,6,7,8,9,10 as empty positions. Among them we can fill positions 2 and 3 from nodes b or c only (hence 2 ways) and remaining 6 places can be filled by e,g,i,f,h,j  such that relative ordering e-g-i and f-h-j must be maintained, this can be done in 6!/(3!3!) = 20 ways. 

Total topological orderings = 2 x 20 = 40

---

thanks @Nirmal Gaur

 

---

refer to this: https://gateoverflow.in/285489/me-test-series

Answer 1

https://medium.com/@WindUpDurb/on-partial-ordering-total-ordering-and-the-topological-sort-9f9c0d0d812f

You may refer this blog and read few topics 

A DAG Is A Poset

Total Ordering

A Total Ordering of a Poset

actually, the incomparable elements ( or you can say simultaneous action) can be ordered in any order. So topological sort is the best way to perform one action after other. Made easy answer is correct. Answer must be 40.