Definition - Baum

• Typen:
  • Wurzelbaum
  • Aufspannender Baum
  • Gerichteter Baum
• Beispiele:
  • Baumdiagramm (Wahrscheinlichkeitsbaum)
• Konstrukte:
  • Blatt
  • Kanonische Wurzel
• Generalisierungen:
  • Graph
  • Wald
• Eigenschaften:
  • Wege maximaler Länge enden in einem Blatt
  • Baum mit mindestens 2 Knoten hat mindestens 2 Blätter
  • Hinzufügen oder Löschen von Blättern ist strukturerhaltend
  • Bäume sind isomorph genau dann, wenn sie den gleichen Code aufweisen
• Hinreichende Aussagen:
  • Zusammenhangskomponenten eines Waldes sind Bäume
• Charakterisierungen:
  • Proposition - T ist ein Baum genau dann wenn es einen eindeutigen Weg zwischen allen Knoten gibt
  • Über den Zusammenhang
    • Proposition - T ist ein Baum genau dann wenn T zusammenhängend ist und eine Kante weniger als Knoten hat
    • Proposition - T ist ein Baum genau dann wenn T zusammenhängend ist und das Wegnehmen einer beliebigen Kante den Zusammenhang zerstört
  • Über Kreisfreiheit
    • Proposition - T ist ein Baum genau dann wenn T kreisfrei ist und eine Kante weniger als Knoten hat
    • Proposition - T ist ein Baum genau dann wenn T kreisfrei ist und das Hinzufügen einer beliebigen Kante zu einem Kreis führt
• Involvierte Definitionen:
  • Graph
  • Zusammenhang
  • Kreis
  • Kreisfreiheit
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Baum

Sei ein Graph.

Ist zusammenhängend und enthält keine Kreise, so bezeichnen wir als Baum (Tree).

Visualisieren wir einen Baum, so wächst dieser immer von oben nach unten. Die Wurzel ist also oben, die Blätter sind unten.

Anmerkung

Bäume und Wälder

Für nicht-zusammenhängende vollständige Graphen, sie auch Wald