Page 649 - Discrete Mathematics and Its Applications

628 9 / Relations

cannot be started until a has been completed. To produce a schedule for the project, we need to
produce an order for all 20 tasks that is compatible with this partial order. We will show how
this can be done.
We begin with a definition. A total ordering is said to be compatible with the partial
ordering R if a b whenever aRb. Constructing a compatible total ordering from a partial
∗
ordering is called topological sorting. We will need to use Lemma 1.

LEMMA 1 Every finite nonempty poset (S, ) has at least one minimal element.

Proof: Choose an element a 0 of S.If a 0 is not minimal, then there is an element a 1 with a 1 ≺ a 0 .
If a 1 is not minimal, there is an element a 2 with a 2 ≺ a 1 . Continue this process, so that if a n is
not minimal, there is an element a n+1 with a n+1 ≺ a n . Because there are only a finite number
of elements in the poset, this process must end with a minimal element a n .

The topological sorting algorithm we will describe works for any finite nonempty poset.
To define a total ordering on the poset (A, ), first choose a minimal element a 1 ; such an
element exists by Lemma 1. Next, note that (A −{a 1 }, ) is also a poset, as the reader should
verify. (Here by we mean the restriction of the original relation on A to A −{a 1 }.) If it is
nonempty, choose a minimal element a 2 of this poset. Then remove a 2 as well, and if there are
additional elements left, choose a minimal element a 3 in A −{a 1 ,a 2 }. Continue this process by
choosing a k+1 to be a minimal element in A −{a 1 ,a 2 ,...,a k }, as long as elements remain.
Because A is a finite set, this process must terminate. The end product is a sequence of
elements a 1 ,a 2 ,...,a n . The desired total ordering t is defined by

a 1 ≺ t a 2 ≺ t ··· ≺ t a n .

This total ordering is compatible with the original partial ordering. To see this, note that if b ≺ c
in the original partial ordering, c is chosen as the minimal element at a phase of the algorithm
where b has already been removed, for otherwise c would not be a minimal element. Pseudocode
for this topological sorting algorithm is shown in Algorithm 1.

ALGORITHM 1 Topological Sorting.

procedure topological sort ((S, ): finite poset)
k := 1
while S =∅
a k := a minimal element of S {such an element exists by Lemma 1}
S := S −{a k }
k := k + 1
return a 1 ,a 2 ,...,a n {a 1 ,a 2 ,...,a n is a compatible total ordering of S}

EXAMPLE 26 Find a compatible total ordering for the poset ({1, 2, 4, 5, 12, 20}, |).

∗ “Topological sorting” is terminology used by computer scientists; mathematicians use the terminology “linearization of a
partial ordering” for the same thing. In mathematics, topology is the branch of geometry dealing with properties of geometric
figures that hold for all figures that can be transformed into one another by continuous bijections. In computer science, a
topology is any arrangement of objects that can be connected with edges.