Definition - Aufspannender Baum

• Konstrukte:
  • Aufspannender Wald
  • Minimal aufspannender Baum
• Generalisierungen:
  • Baum
• Eigenschaften:
  • Satz von Cayley
• Hinreichende Aussagen:
  • Kruskal-Algorithmus (Die Sortierung der Kanten ist jedoch egal, da es keine Gewichte gibt.)
• Involvierte Definitionen:
  • Graph
  • Zusammenhang
  • Teilgraph
  • Baum
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Aufspannender Baum

Sei ein zusammenhängender Graph.
Sei ein Teilgraph von .
Sei insbesondere .

Ist außerdem ein Baum, so bezeichnen wir auch als aufspannenden Baum für .

Anmerkung

Tipp bzgl. der Kantenmenge

Da ein Teilgraph von ist, gilt auch .