Definition: Trees and Forests
Let \(G(V,E,\gamma)\) be an undirected graph.
* \(G\) is called a forest, if it contains only acyclic components.
* \(G\) is called a tree, if it has only one acyclic component.
Table of Contents
- Proposition: Equivalent Definitions of Trees
- Definition: Root, Degree of a Tree, Subtree, Height
- Lemma: Lower Bound of Leaves in a Tree
- Lemma: Relationship between Tree Degree, Tree Height and the Number of Leaves in a Tree
- Definition: Spanning Tree
- Definition: Graph Decomposable Into \(k\) Trees
Definitions: 2 3 4 5
Lemmas: 7 8 9 10
Proofs: 11 12 13 14 15 16 17 18
- Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition