# Topological Sorting in Linear Order for Hasse Diagram

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:

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!

-

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.

-
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