Exercises 19.8 Exercises
Recognizing a partial order from its graph.
In each of Exercises 1β2, you are given a directed graph for a relation on the set Determine whether the relation is a partial order. Justify your answers.
2.
Testing partial orders.
In each of Exercises 3β6, you are given a set and a relation on Determine whether the relation is a partial order. Justify your answers.
Drawing Hasse diagrams.
In each of Exercises 7β8, you are given a finite, partially ordered set Draw the Hasse diagram.
9.
Draw all possible valid Hasse diagrams for each of the sets and (Thus, you will have determined all possible partial orders on those sets.)
10.
(a)
that is finite, and on which is a total order.
(b)
that is infinite, and on which is a total order.
(c)
on which is a partial order but not a total order.
11.
Determining maximal/maximum/minimal/minimum elements.
In each of Exercises 12β16, you are given a partially ordered set Determine any and all maximal, maximum, minimal, and minimum elements.
17.
Suppose is a partial order on the set such that is a maximal element. What are the possibilities for the Hasse diagram of
Topological sorting.
In each of Exercises 18β19, you are given the Hasse diagram for a partially ordered set Use the Topological sorting algorithm to determine a compatible total order on