Mathematics for Computer Science

9.5. Directed Acyclic Graphs & Partial Orders 243

Remembering that a digraph is a binary relation on its vertices, it makes sense

to compose a digraphGwith itself. Then if we letGndenote the composition of

Gwith itselfntimes, it’s easy to check (see Problem 9.8) thatGnis thelength-n

walk relation:

a Gnb iff there is a length-nwalk inGfromatob:

This even works fornD 0 , with the usual convention thatG^0 is the identity relation

IdV.G/on the set of vertices.^3 So now we have^4

GDG^0 [G^1 [G^2 [:::[GjV.G/j^1 D.G[G^0 /jV.G/j^1 : (9.9)

The final equality points to the use of repeated squaring as a way to computeG

with lognrather thann 1 compositions of relations.

9.5 Directed Acyclic Graphs & Partial Orders

Definition 9.5.1.Adirected acyclic graph (DAG)is a directed graph with noposi-

tivelength cycles.

DAG’s come up constantly because, among other things, they model task schedul-

ing problems, where nodes represent tasks to be completed and arrows indicate

which tasks must be completed before others can begin. For example, Figure 9.6

shows the prerequisite structure among MIT computer science subjects.

A positive length cycle in a prerequisite graph like this would have a dire effect

on the time it takes to graduate.

The relationship between walks and paths extends to closed walks and cycles.

Lemma 9.5.2.The shortest positive length closed walk through a vertex is a cycle

through that vertex.

(^3) The identity relation, IdA, on a set,A, is the equality relation:
aIdAb iff aDb;
fora;b 2 A.
(^4) Equation (9.9) involves a harmless abuse of notation: we should have written
graph.G/Dgraph.G^0 /[graph.G^1 /::::