Ein Baum ist ein zusammenhängender, azyklischer, ungerichteter Graph.
Eigenschaften
- Für einen Baum mit $n$ Knoten gilt: Anzahl Kanten $=n-1$.
- Zwischen je zwei Knoten existiert genau ein einfacher Weg.
- Äquivalent: zusammenhängend + keine Zyklen oder minimal zusammenhängend (Entfernt man eine Kante, wird er unzusammenhängend).
Beispiel
Hier ist $A$ die Wurzel; es gibt keine Zyklen und für jeden Knoten genau einen Pfad zur Wurzel.