|
|
|
|
acyclic graph
|
(Definition)
|
|
|
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.
In contrast, the following graph and digraph are not acyclic, because each contains a cycle.
|
"acyclic graph" is owned by Logan.
|
|
(view preamble)
See Also: graph, cycle
| Other names: |
acyclic, DAG |
| Also defines: |
directed acyclic graph |
Pronunciation (guide):
|
|
Cross-references: digraph, cycles, contains, graph
There are 4 references to this entry.
This is version 5 of acyclic graph, born on 2002-03-02, modified 2002-03-02.
Object id is 2746, canonical name is AcyclicGraph.
Accessed 12449 times total.
Classification:
| AMS MSC: | 05C38 (Combinatorics :: Graph theory :: Paths and cycles) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![\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}](http://images.planetmath.org:8080/cache/objects/2746/l2h/img1.png "\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}")
![\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}](http://images.planetmath.org:8080/cache/objects/2746/l2h/img2.png "\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}")