acyclic graphAcyclicGraph2002-03-02 12:32:352002-03-02 17:16:01Definition/a-sik'lik/directed acyclic graph\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[all]{xy}Any graph that contains no cycles is an \emph{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 \emph{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}
$$