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.

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|improve this question

1 Answer 1

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|improve this answer
    
Thank you so much I really appreciate it!! –  pyramid Apr 9 '13 at 0:34
1  
@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

 
discard

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.