Minimaler Spannbaum

Ein Spannbaum mit minimalem Gewicht heißt minimaler Spannbaum (eng. minimum spacing tree, MST):

Einfach gesagt

Unter allen möglichen Spannbäumen, wenn man das Gewicht des Spannbaums aufsummiert, sind die minimalen Spannbäume die mit dem kleinsten Gewicht.

Es kann mehrere minimale Spannbäume mit unterschiedlichen Kanten geben.

Implementierung

Greedy-Algorithmus zum Finden eines MST:

• GENERIC_GREEDY_MST( ,)
  • MST() =
  • Solange 𝐴 noch kein MST von ist
    • Wähle eine geeignete Kante , die zu hinzugefügt werden kann
    • MST() = MST() {}

Minimalbaum-Eigenschaft

Sei ein zusammenhängender, ungerichteter, kantengewichteter Graph. Sei eine echte, nichtleere Teilmenge der Knoten.

Satz: Sei eine Kante mit minimalem Gewicht mit und , dann gibt es einen minimalen Spannbaum mit .

Das ist die Korrektheitsbedingung für Kruskal-Algorithmus und Prim-Algorithmus