Page 650 - Discrete Mathematics and Its Applications

9.6 Partial Orderings 629

12 20 12 20 12 20 12 20 12 20 12

4 4 4
4
2
5 2 5 2
1

Minimal
element 1 5 2 4 20 12
chosen

FIGURE 9 A Topological Sort of ({1, 2, 4, 5, 12, 20}, |).

Solution: The first step is to choose a minimal element. This must be 1, because it is the only
minimal element. Next, select a minimal element of ({2, 4, 5, 12, 20}, |). There are two minimal
elements in this poset, namely, 2 and 5. We select 5. The remaining elements are {2, 4, 12, 20}.
The only minimal element at this stage is 2. Next, 4 is chosen because it is the only minimal
element of ({4, 12, 20}, |). Because both 12 and 20 are minimal elements of ({12, 20}, |), either
can be chosen next. We select 20, which leaves 12 as the last element left. This produces the
total ordering

1 ≺ 5 ≺ 2 ≺ 4 ≺ 20 ≺ 12.

The steps used by this sorting algorithm are displayed in Figure 9. ▲

Topological sorting has an application to the scheduling of projects.

EXAMPLE 27 A development project at a computer company requires the completion of seven tasks. Some of
these tasks can be started only after other tasks are finished. A partial ordering on tasks is set up
by considering task X ≺ task Y if task Y cannot be started until task X has been completed. The
G Hasse diagram for the seven tasks, with respect to this partial ordering, is shown in Figure 10.
Find an order in which these tasks can be carried out to complete the project.
D F
Solution: An ordering of the seven tasks can be obtained by performing a topolog-
ical sort. The steps of a sort are illustrated in Figure 11. The result of this sort,
B
A ≺ C ≺ B ≺ E ≺ F ≺ D ≺ G, gives one possible order for the tasks. ▲
A C E
G G G G G G G
FIGURE 10 The
Hasse Diagram for D F D F D F D F D F D
Seven Tasks.

B B B
A C E C E E E

Minimal
element A C B E F D G
chosen

FIGURE 11 A Topological Sort of the Tasks.