For certain applications it is convenient to deal with graphs that contain no cycles. For example, a tree (see Chapter ) is a special kind of graph that contains no cycles.

Definition (Directed Acyclic Graph (DAG))A

directed, acyclic graphis a directed graph that contains no cycles.

Obviously, all trees are DAGs. However, not all DAGs are trees. For example consider the two directed, acyclic graphs, and , shown in Figure . Clearly is a tree but is not.

**Figure:** Two Directed, Acyclic Graphs

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.