Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

216 DIRECTED GRAPHS [CHAP. 9

Fig. 9-14

Fig. 9-15

9.9Directed Cycle-Free Graphs, Topological Sort

LetSbe a directed graph with the following two properties:

(1) Each vertexviofSrepresents a task.

(2) Each (directed) edge(u, v)ofSmeans that taskumust be completed before beginning taskv.

We note that such a graphScannot contain a cycle, such asP =(u, v, w, u), since, otherwise, we would have
to completeubefore beginningv, completevbefore beginningw, and completewbefore beginningu. That is,
we cannot begin any of the three tasks in the cycle.
Such a graphS, which represents tasks and a prerequisite relation and which cannot have any cycles, is
said to becycle-freeoracyclic. A directed acyclic (cycle-free) graph is called adagfor short. Figure 9-16 is an
example of such a graph.