Baum, (minimaler) spannender

Jeder Teilgraph eines Graphen G, der dieselbe Menge Knoten wie G besitzt und ein Baum ist, heißt spannender Baum von G.

Weist ein solcher Teilgraph die kleinstmögliche Summe der Kantenbewertungen auf, ist er ein minimaler spannender Baum von G. Minimale spannende Bäume sind z.B. bei der Einrichtung von Rohrleitungssystemen oder Computernetzen von Interesse, wo jeder Knoten (Wasserverbraucher, Arbeitsstation) mit jedem anderen kostengünstig verknüpft werden muss. Die Bestimmung des minimalen spannenden Baums erfolgt auf einfache Weise z.B. mit Hilfe des Kruskal-Algorithmus.

<< vorhergehender Begriff

nächster Begriff >>

Baum

Baum-Algorithmus