Definition - Minimal aufspannender Baum

• Generalisierungen:
  • Aufspannender Baum
• Hinreichende Aussagen:
  • Kruskal-Algorithmus
• Involvierte Definitionen:
  • Aufspannender Baum
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Minimal aufspannender Baum

Sei ein zusammenhängender Graph.
Die Kanten seien außerdem mit Gewichten (in ) ausgestattet. Hierfür sei die Gewichtsfunktion.

Als minimalen aufspannende Baum bezeichnen wir denjenigen Spannbaum, der das niedrigste Gewicht hat. Also: