Question

To determine all compatible total ordering for the poset \((\{ 1,2,4,5,12,20\} ,)\).

Short answer

The compatible total ordering for the poset is

\(\begin{array}{l}1 \prec 5 \prec 2 \prec 4 \prec 12 \prec 20\\1 \prec 2 \prec 5 \prec 4 < 12 \prec 20\\1 \prec 2 \prec 4 \prec 5 < 12 \prec 20\\1 \prec 2 \prec 4 < 12 < 5 < 20\\1 \prec 5 \prec 2 \prec 4 < 20 < 12\\1 \prec 2 \prec 5 < 4 < 20 < 12\\1 \prec 2 \prec 4 \prec 5 < 20 \prec 12\end{array}\)

Step-by-step solution

Given data

Poset is \((\{ 1,2,4,5,12,20\} ,1)\).

Concept used of Topological sorting

Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices\({v_1},{v_2}, \ldots {v_n}\)in such a way, that if there is an edge directed towards vertex\({v_j}\)from vertex\({v_i}\), then\({v_i}\)comes before\({v_j}\).

Find the compatible total order

We have a poset \((\{ 1,2,4,5,12,20\} ,\mid )\) and we have to find all the compatible total orderings. There is no specific method to find the total orderings rather it is a simple method to find out this total orderings, we will represent all the total orderings in

a table below

Hence, the compatible total ordering for the poset is

\(\begin{array}{l}1 \prec 5 \prec 2 \prec 4 \prec 12 \prec 20\\1 \prec 2 \prec 5 \prec 4 < 12 \prec 20\\1 \prec 2 \prec 4 \prec 5 < 12 \prec 20\\1 \prec 2 \prec 4 < 12 < 5 < 20\\1 \prec 5 \prec 2 \prec 4 < 20 < 12\\1 \prec 2 \prec 5 < 4 < 20 < 12\\1 \prec 2 \prec 4 \prec 5 < 20 \prec 12\end{array}\).