Chapter 9 Directed graphs & Partial Orders250
That is, ifR 1 andR 2 both have one of these properties, then so doesR 1 R 2. This
implies that ifR 1 andR 2 are both partial orders, then so isR 1 R 2.
On the other hand, the property of being a path-total order is not preserved. For
example, the age-height relationY is the product of two path-total orders, but it
is not path-total: the age 240 months, height 68 inches pair, (240,68), and the pair
(228,72) are incomparable underY.
9.10 Scheduling
Scheduling problems are a common source of partial orders: there is a set,A, of
tasks and a set of constraints specifying that starting a certain task depends on
other tasks being completed beforehand. We can picture the constraints by drawing
labelled boxes corresponding to different tasks, with an arrow from one box to
another if the first box corresponds to a task that must be completed before starting
the second one.
For example, the DAG for in Figure 9.7 describes how a guy might get dressed
for a formal occasion. The vertices correspond to garments and the edges specify
which garments have to be put on before others are.
When we have a partial order like this on the order in which tasks can be per-
formed, it can be useful to have an order in which to perform all the tasks, one at a
time, while respecting the dependency constraints. This amounts to finding a path-
total order that is consistent with the partial order. This task of finding a path-total
ordering that is consistent with a partial order is known astopological sorting.
Definition 9.10.1. Atopological sortof a partial order, , on a set,A, is a path-
total ordering,@, onAsuch that
a b IMPLIES a@b:
There are several path-total orders that are consistent with the partial order shown
in Figure 9.7. We have shown two of them in list form in Figure 9.8. Each such
list is a topological sort for the partial order in Figure 9.7. In what follows, we
will prove that everyfiniteposet has a topological sort. You can think of this as a
mathematical proof that youcanget dressed in the morning (and then show up for
math lecture).
Topological sorts for partial orders on finite sets are easy to construct by starting
fromminimalelements:
Definition 9.10.2. Letbe a partial order on a set,A. An elementa 02 Ais
minimumiff it isevery other element ofA, that is,a 0 bfor allb¤a 0.
