Forest

 

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  components and  nodes has  graph edges. The numbers of forests on , 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 , 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.

---

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

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

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