Acyclic Graph

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 graph.

---

REFERENCES

Skiena, 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."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength