This is a place holder for potential sponsor logos.

acyclic graph

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

In contrast, the following graph and digraph are not acyclic, because each contains a cycle.

$\begin{displaymath} \begin{array}{cc} \xymatrix{&A\ar@{-}[dl]\ar@{-}[dr]\\ B\ar@... ...d & \quad \xymatrix{&A\ar[dr]\\ B\ar[ur]&&C\ar[ll]} \end{array}\end{displaymath}$

acyclic graph is owned by Logan Hanks.

How to Cite This Entry

Logan Hanks. "acyclic graph" (version 5). PlanetMath.org. Freely available at http://planetmath.org/AcyclicGraph.html.

Classification

AMS MSC:

05C38 (Combinatorics :: Graph theory :: Paths and cycles)

Pending Errata and Addenda

None.

Interact

Discussion

No messages.

Username:
Password:

Register
I've forgotten my login details