vorige nächste

minimal spanning tree


Ein wichtiges Suchproblem läßt sich im Graphen dadurch beschreiben, dass zu einem zusammenhängenden Graphen ein immer noch zusammenhängender Teilgraph minimaler Länge gesucht wird.

Dabei wird man in der Regel einen bewerteten Graphen haben, so dass nicht allein die Zahl der auftretenden Kanten interessiert, sondern ihre Gesamtkosten. Ein typisches Beispiel ist die Aufgabe, ein minimales Versorgungsnetz aufzubauen, also ein nicht redundantes Netz (also eigentlich gar kein Netz!), bei dem der Ausfall eines Netzabschnittes nicht durch die Versorgung über einen Umweg kompensiert werden kann.

Für den Aufbau eines solchen Versorgungsnetzes fallen Kosten an, die in der Regel zumindest von der Länge der Teilverbindungen abhängig sind. Bilden wir einen Graphen zur Beschreibung dieses Netzes, dann sind den Kanten diese Kosten zuzuordnen. Allgemein wird für die Kantenbewertung in Graphen daher häufig der Begriff Kosten verwendet. Das Ziel in vielen Anwendungsfällen wird sein, die durch das Netz entstehenden Gesamtkosten zu minimieren.

Definition minimal spanning tree
Ein Graph heißt minimaler aufspannender Baum zu einem Graphen, wenn es keinen anderen Teilgraphen mit geringeren Kosten gibt, der auch aufspannender Baum ist.

Als erster Teilbegriff tritt hierbei der Begriff des aufspannenden Baumes auf.

Ein Graph ist ein Baum, wenn es zwischen je zwei seiner Ecken genau einen Weg gibt, in ihm also keine Zyklen auftreten.

Bei der Begriffsbildung des aufspannenden Baumes geht man zunächst von irgendeinem zusammenhängenden Graphen aus und entfernt aus ihm solche Kanten, ohne die er immer noch zusammenhängend bleibt, bis er ein Baum geworden ist. Da die Auswahl der Kanten dabei aber nicht vorgegeben ist, können aus einem vorgegebenen Graphen -wie das folgende Beispiel zeigt- verschiedene Bäume entstehen.