Minimalen Spannbaum
Minimaler Spannbaum
Zusammenfassung
Für einen Graphen mit gewichteten Kanten ist ein minimaler Spannbaum (MST) ein Spannbaum der Kantengewichtsumme minimiert.
Def. Minimaler Spannbaum
Es sei $G = (V, E)$ ein zusammenhängender Ungerichteter Graph und $w : E → R$ eine (Kanten-) Gewichtsfunktion. Ein minimaler Spannbaum (MST) von $G = (V, E)$ ist ein spannender Baum $T = (V, ET )$ von $G$ mit minimalem Gesamtgewicht
$$w(T)=\sum_{c\in E_T}w(e)\;.$$
Algorithmen welche den MST finde sind: