|
Any graph that contains no cycles is an acyclic graph. A directed acyclic graph is often called a DAG for short.
For example, the following graph and digraph are acyclic.
$$ \begin{array}{cc} \xymatrix{&A\ar@{-}[dl]\ar@{-}[dr]\\B&&C} \quad & \quad \xymatrix{&A\ar[dr]\\B\ar[ur]\ar[rr]&&C} \end{array} $$
In contrast, the following graph and digraph are not acyclic, because each contains a cycle.
$$ \begin{array}{cc} \xymatrix{&A\ar@{-}[dl]\ar@{-}[dr]\\B\ar@{-}[rr]&&C} \quad & \quad \xymatrix{&A\ar[dr]\\B\ar[ur]&&C\ar[ll]} \end{array} $$
|