Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have come across an exam review question that I am stuck on. The question states:

Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram:

Hasse diagram

This is what I was able to come up with: e, c, b, j, m, l, a, i, k, d, u, t, s, r, g, o, h, p, f, n

I am also certain this isn't correct..

Any Explanation is much appreciated!

share|cite|improve this question
up vote 1 down vote accepted

Note that $h$ is the minimum element in that partial order, so it must precede every other element in any compatible linear order. Delete $h$ and its outgoing edges from the Hasse diagram; what’s left has two minimal elements, $p$ and $o$, and you can put either of them next after $h$ in the linear order. I’ll take $p$ next, so at this point my (partial) linear order is $hp$. Delete $p$ and its outgoing edges; the remaining Hasse diagram has minimal elements $j$, $f$, and $o$, and you can put any of them next after $p$. I’ll use $o$, so my linear order is now $hpo$. After I remove $o$ and its outgoing edges, the Hasse diagram that remains has minimal elements $j$, $f$, $n$, and $g$, and I can put any of them after $o$ in my linear order.

Now just continue the procedure until you’ve exhausted the vertices. There is more than one compatible linear order.

share|cite|improve this answer
Thank you so much I really appreciate it!! – pyramid Apr 9 '13 at 0:34
@pyramid: You’re welcome! – Brian M. Scott Apr 9 '13 at 0:36
Hi Mr. Scott, I have one more question relating to this graph if I may. Would the greatest lower bound of {u, k, m} be "f"? And for {p,k,} be "p"? Thanks for your time! – pyramid Apr 10 '13 at 0:13
@pyramid: Yes, both of those are correct. – Brian M. Scott Apr 10 '13 at 0:17

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.