Direkt zum Inhalt

Lexikon der Mathematik: spannender Baum

Gerüst, erzeugender Baum, Begriff aus der Graphentheorie. Ein spannender Baum eines Graphen G ist ein Faktor T von G, der ein Baum ist.

Schon im Jahre 1847 hat G.R. Kirchhoff gezeigt, daß jeder zusammenhängende Graph ein Gerüst besitzt. Ein Faktor H von G heißt spannender Wald von G, wenn H ein Wald ist. Ist G ein zusammenhängender bewerteter Graph mit einer Bewertung ρ ϱ: K(G) → ℝ, so nennt man einen spannenden Baum T von G, dessen Bewertung ϱ(T) unter allen Gerüsten minimal ist, einen minimal spannenden Baum oder minimal erzeugenden Baum von G. Ist G nicht zusammenhängend, so nennt man einen spannenden Wald H von G, der die gleiche Anzahl von Zusammenhangskomponenten wie G aufweist, und dessen Gesamtbewertung ϱ(H) unter allen solchen spannenden Wäldern minimal ist, einen minimal spannenden Wald oder minimal erzeugenden Wald. Bei der Konstruktion eines minimal spannenden Waldes kann man sich auf das minimal-spannende-Baum-Problem oder MST-Problem („minimum spanning tree Problem“) zurückziehen, indem man sich für jede Zusammenhangskomponente von G einen minimal spannenden Baum beschafft. Zur Bestimmung solcher minimal spannenden Bäume bieten sich vor allen Dingen die Algorithmen von Kruskal und Prim an (Kruskal, Algorithmus von, Prim, Algorithmus von).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos