Gerüst, erzeugender Baum, Begriff aus der Graphentheorie. Ein spannender Baum eines GraphenG 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).