◀ ▲ ▶Branches / Graph-theory / Definition: Trees and Forests

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

1. Proposition: Equivalent Definitions of Trees
2. Definition: Root, Degree of a Tree, Subtree, Height
3. Lemma: Lower Bound of Leaves in a Tree
4. Lemma: Relationship between Tree Degree, Tree Height and the Number of Leaves in a Tree
5. Definition: Spanning Tree
6. Definition: Graph Decomposable Into \(k\) Trees

Mentioned in:

Branches: 1
Definitions: 2 3 4 5
Examples: 6
Lemmas: 7 8 9 10
Proofs: 11 12 13 14 15 16 17 18
Propositions: 19

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition