in Set Theory & Algebra
742 views
2 votes
2 votes

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

in Set Theory & Algebra
742 views

4 Comments

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

1
1

thanks @Nirmal Gaur

 

0
0
0
0

1 Answer

0 votes
0 votes

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. 

 

Related questions

0 votes
0 votes
1 answer
1
Shankar Kakde asked in Set Theory & Algebra Jan 10, 2019
180 views
Shankar Kakde asked in Set Theory & Algebra Jan 10, 2019
180 views
0 votes
0 votes
0 answers
2
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4