Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I was assigned this problem for homework and I was able to all of them except for part D I would really appreciate any help or hintsenter image description here I have no clue where to start I looked through my book and everything anything would be appreciated

share|improve this question

1 Answer 1

We need to obtain a total ordering such that whenever $a < b$ in the partial ordering, we also have $a<b$ in this total ordering. Looking at the Hasse diagram, just pick out the minimal elements one by one. If there is more than one minimal element, pick any one arbitrarily. For example, first pick $e$ say, then $f, c,d,b,a$. This ordering $e<f<c<d<b<a$ is a total ordering compatible with the given partial ordering. Another order is $f,e,d,c,b,a$. In all cases, $e$ would be before $b$ and before $c$, $f$ would be before $c$ and before $d$, and $a$ would be last. This algorithm of removing minimal elements one by one is called topological sort.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.