Minimale Gerüste

MST (minimum spanning tree, Minimalgerüst):

• Eingabe: zusammenhängender ungerichteter Graph G, Kantengewichtsfunktion w : E(G)$\to$$\mathbb {Q}$
• Ausgabe: eine Gerüst T von G mit minimalem Gewicht w(T) = $\Sigma${w(e) | e $\in$ E(T)}.

Anwendungen bei Planung von (Versorgungs-)Netzen:

• G sind gewünschte Verbindungen,
• T sind die tatsächlich herzustellenden,
• w(e) sind die Herstellungskosten (nicht: die Nutzungskosten).