Discrete Mathematics for Computer Science

200 CHAPTER 3 Relations

3.8.6 Application: Embedding a Partial Order

One fairly typical application of partial orderings is to schedule a set T of tasks. Usually, a

set of tasks includes requirements that certain tasks be completed before others begin. If it

is possible to do the tasks so that all the constraints are satisfied, these requirements may be

treated as a partial ordering R on the set of tasks where, for x, y E T, we have (x, y) E R

if and only if x must be completed before y may be begun.

Schedules to do these tasks, on the other hand, are often linear orders, since normally,

only one task can be done at a time. Hence, there is a problem of finding a linear ordering

S of T so that, if x R y and x A y, then x S y. This clearly amounts to finding a linear

ordering S so that R - IdT g S. For the partial ordering shown in Figure 3.17, the linear

ordering S could consist of the pairs {(A, B), (B, D), (D, C), (C, E), (E, F)} together

with the pairs needed to make the relation transitive. Another linear order that would satisfy

the condition consists of the pairs {(A, C), (C, B), (B, F), (F, E), (E, D)} together with

the other pairs needed to make the relation transitive. The process of finding a linear order

associated with a partial order is called embedding a partial order in a linear order.

Example 13. Construct a schedule for logging on to a computer and both checking email

and modifying a text file. Checking email includes opening the mailer and both replying

to a new message and creating a new message to another person. Modifying the text file

involves opening a text editor, loading a file, editing the first paragraph of the file, inserting

a separate file at the end of the file, and saving the modified file. The user is allowed to

move back and forth between the mailer and the text editor for separate tasks.

Solution. First, draw a diagram representing the dependency among various activities:

a Logon

Open Open Text

Mailer b e Editor

c 'd f Open File

Reply Send New

Msg. Insert

Modify 'h Ext. File

File

Save

Modified

File

Partial order

Next, find a linear order that embeds this partial order. One result is shown here: