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.