PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
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.

$$ \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} $$




"acyclic graph" is owned by Logan.
(view preamble | get metadata)

View style:

See Also: graph, cycle

Other names:  acyclic, DAG
Also defines:  directed acyclic graph

Pronunciation (guide):
 acyclic: /a-sik'lik/
Log in to rate this entry.
(view current ratings)

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 17630 times total.

Classification:
AMS MSC05C38 (Combinatorics :: Graph theory :: Paths and cycles)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)