acyclic graph

Primary tabs

For example, the following graph and digraph are acyclic.

\begin{array}[]{cc}\xymatrix{\hfil&A\ar@{-}[dl]\ar@{-}[dr]\\ B&&C&\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{\hfil&A\ar@{-}[dl]\ar@{-}[dr]\\ B\ar@{-}[rr]&&C&\xymatrix{&A\ar[dr]\\ B\ar[ur]&&C\ar[ll]\end{array}

Defines:

directed acyclic graph

Synonym:

acyclic, DAG

Type of Math Object:

Definition

Major Section:

Reference