Download Wolfram Notebook

A forest is a finite simple graph that is undirected and acyclic (i.e., has no graph cycles). Forests therefore consist only of (possibly disconnected) trees, hence the name "forest."

Examples of forests include the singleton graph, empty graphs, and all trees.

A forest with components and nodes has graph edges. The enumerations below count forests up to graph isomorphism. The numbers of forests on , 2, ... nodes are 1, 2, 3, 6, 10, 20, 37, ... (OEIS A005195).

An undirected graph can be tested to determine if it is acyclic (i.e., a forest) in the Wolfram Language using AcyclicGraphQ[g]. A collection of acyclic graphs is available as GraphData["Acyclic"] or GraphData["Forest"].

The total numbers of trees in all the forests of orders , 2, ... are 1, 3, 6, 13, 24, 49, 93, 190, 381, ... (OEIS A005196). The average numbers of trees are therefore 1, 3/2, 2, 13/6, 12/5, 49/20, 93/37, 5/2, ... (OEIS A095131 and A095132).

The triangle of numbers of -node forests containing trees is 1; 1, 1; 1, 1, 1; 2, 2, 1, 1; 3, 3, 2, 1, 1; ... (OEIS A095133).

Connected forests are trees.

See also

Acyclic Digraph, Connected Graph, Graph Cycle, Induced Forest, Pseudoforest, Spanning Forest, Tree

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 32, 1994.Palmer, E. M. and Schwenk, A. J. "On the Number of Trees in a Random Forest." J. Combin. Th. B 27, 109-121, 1979.Skiena, S. "Acyclic Graphs." §5.3.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 188-190, 1990.Sloane, N. J. A. Sequences A005195/M0776, A005196/M2567, A095131, A095132, and A095133 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Forest

Cite this as:

Weisstein, Eric W. "Forest." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Forest.html

Subject classifications