Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders246

9.6 Weak Partial Orders

Partial orders come up in many situations which on the face of it have nothing to do

with digraphs. For example, the less-than order,<, on numbers is a partial order:

 ifx < yandy < zthenx < z, so less-than is transitive, and

 ifx < ytheny 6 < x, so less-than is asymmetric.

The proper containment relationis also a partial order:

 ifABandBCthenAC, so containment is transitive, and

 A6A, so proper containment is irreflexive.

Partial orders have particular importance in computer science because, besides

modeling task scheduling problems, they capture key concepts used, for example,

in analyzing concurrency control, as illustrated in Section 9.10.

The less-than-or-equal relation,, is at least as familiar as the less-than strict

partial order, and the ordinary containment relation,, is even more common than

the proper containment relation. These are examples ofweak partial orders.

Definition 9.6.1.A relationRon a set,A, is a weak partial order iff there is a strict

partial order,S, onAsuch that

a R b iff .a S b ORaDb/;

for alla;b 2 A.

Weak partial orders can also be defined in terms of relational properties. We just

have to relax the asymmetry property to allow each element to be related to itself;

this property is calledantisymmetry:

Definition 9.6.2.A binary relation,R, on a setA, isantisymmetriciff

a R b IMPLIES NOT.b R a/

for alla¤b 2 A.

A relation isweak partial order^5 iff it is transitive, reflexive, and antisymmetric.

(^5) Some authors define partial orders to be what we call weak partial orders, but we’ll use the phrase
“partial order” to mean either a weak or strict one.