An acyclic graph is a graph having no graph cycles.
Acyclic graphs are bipartite.
A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is
known as a forest (i.e., a collection of trees).
The numbers of acyclic graphs (forests) on , 2, ... are 1, 2, 3, 6, 10, 20, 37, 76, 153, ... (OEIS A005195), and the corresponding numbers of connected
acyclic graphs (trees) are 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, ... (OEIS A000055).
A graph can be tested in the Wolfram Language to see if it is acyclic using AcyclicGraphQ[g],
and a collection of acyclic graphs are available as GraphData["Acyclic"].
A graph with a single cycle is known as a unicyclic
See alsoCyclic Graph
, Graph Cycle
Explore with Wolfram|Alpha
ReferencesSkiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, p. 190, 1990.Sloane, N. J. A. Sequences
A000055/M0791 and A005195/M0776
in "The On-Line Encyclopedia of Integer Sequences."
on Wolfram|AlphaAcyclic Graph
Cite this as:
Weisstein, Eric W. "Acyclic Graph." From
MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AcyclicGraph.html