TOPICS
Search

Forest


Forests

A forest is an acyclic graph (i.e., a graph without any 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 k components and n nodes has n-k graph edges. The numbers of forests on n=1, 2, ... nodes are 1, 2, 3, 6, 10, 20, 37, ... (OEIS A005195).

A graph can be tested to determine if it is acyclic (i.e., a forest) in the Wolfram Language using AcylicGraphQ[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 n=1, 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 n-node forests containing k 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, Pseudoforest, 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 Web Resource. https://mathworld.wolfram.com/Forest.html

Subject classifications