24.5.2. Total Ordering and Hasse Diagram

Try these first

1. 1.

   Define a poset.

   Hint

   Think of the properties that a relation needs.

2. 2.

   What does it mean for y to cover x?

   Hint

   Visualize this in a Hasse Diagram.

3. 3.

   What does a Hasse diagram represent?

   • A type of graph
   • A graph showing a poset
   • A sorting algorithm

   Hint

   Think about its purpose.

4. 4.

   True or False? Every poset must have both a least and a greatest element.

   • True
   • False

   Hint

   Consider the definitions of these elements.

5. 5.

   Create a Hasse diagram for the set of integers from 1 to 5 under the relation of 'divides'. Identify minimal and maximal elements.

   Hint

   Take each number and see which others it divides.

6. 6.

   Given a set of tasks: {A, B, C, D}, with dependencies: A must complete before B and C, C must complete before D; demonstrate a topological sort.

   Hint

   Find all paths that respect the order of dependency.