Mathematics for Computer Science

9.5. Directed Acyclic Graphs & Partial Orders 245

The proof is essentially the same as for Theorem 9.2.3 (see Problem 9.6).
The edges in the subject prerequisite DAG of Figure 9.6 show thedirectpre-
requisites listed for each subject, but to enroll for a subject you must of course
have taken the prerequisites of the prerequisites and their prerequisites, and so on.
In other words, ifDis the direct prerequisite relation, then subjectuhas to be
completed before taking subjectviffu DCv.
The condition thatDis a DAG is equivalent to saying that if there is a positive
length path from vertexuto vertexv, there can’t be one fromvback tou. This
relational property is calledasymmetry.

Definition 9.5.3.A binary relation,R, on a set,A, isasymmetriciff

a R b IMPLIES NOT.b R a/

for alla;b 2 A.

A simpler way to say that a graph is a DAG is to say that there is no positive
length path from any vertex to itself. This property is calledirreflexivity.

Definition 9.5.4.A binary relation,R, on a set,A, isirreflexiveiff

NOT.a R a/

for alla 2 A.

Definition 9.5.5.A relation that is transitive and asymmetric is called astrict par-
tial order.

To summarize, we have

Theorem 9.5.6.A relation is a strict partial order iff it is the positive path relation
of a DAG.

Corollary 9.5.7.A relation is a strict partial order iff it is transitive and irreflexive.

A strict partial order may be the positive path relation of different DAG’s. This
raises the question of finding a DAG with thesmallestnumber of edges that deter-
mines a given strict partial order. Forfinitestrict partial orders, the smallest such
DAG turns out to be unique and easy to find (see Problem 9.2).