Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Ein Spannbaum (auch aufspannender Baum oder spannender Baum genannt; englisch spanning tree) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle seine Knoten enthält. Spannbäume existieren nur in zusammenhängenden Graphen.

Einen Teilgraphen, der in (nicht notwendigerweise zusammenhängenden) Graphen für jede Komponente einen Spannbaum ergibt, nennt man Gerüst, Spannwald, aufspannender Wald oder kürzer spannender Wald. In zusammenhängenden Graphen sind Gerüst und Spannbaum also identische Begriffe, während Spannbäume für unzusammenhängende Graphen nicht definiert sind.

In kantengewichteten Graphen lässt sich als Gewicht eines Graphen die Summe seiner Kantengewichte definieren. Ein Spannbaum bzw. ein Gerüst heißt minimal, wenn kein anderer Spannbaum bzw. kein anderes Gerüst in demselben Graphen mit geringerem Gewicht existiert. Häufig kürzt man minimaler Spannbaum auch mit MST (Abkürzung des englischen Begriffs Minimum Spanning Tree) oder MCST (Minimum Cost Spanning Tree - ein Spannbaum mit minimalen Kosten) ab. Statt minimales Gerüst sagt man auch Minimalgerüst.

Das Spannbaumproblem tritt in der Praxis beispielsweise bei der vollständigen Verdrahtung von Kommunikationsnetzen auf (siehe auch Spanning Tree Protocol). Ein beliebiger Spannbaum, der alle Knoten verbindet, löst zwar das Verbindugsproblem, ist aber möglicherweise nicht der kürzeste Weg bzw. nicht optimal. Eine Verbindung, die alle Stationen mit minimaler Weglänge verbindet, ist ein minimaler Spannbaum (MST), man spricht in diesem Fall vom MST-Problem. Für das Problem des Handlungsreisenden existieren Approximationsalgorithmen, die minimale Spannbäume verwenden (MST-Heuristik).

Inhaltsverzeichnis 1 Wichtige Algorithmen 2 Anwendungen 3 Literatur 4 Weblinks 5 Siehe auch

Wichtige Algorithmen

Zum Finden eines minimalen Spannbaumes gibt es u.a. den Algorithmus von Kruskal und den Algorithmus von Prim. Letzterer ist der effizientere und besitzt die Worst-Case-Laufzeit . Allerdings benötigt er dafür eine recht komplexe Datenstruktur, die sogenannten Fibonacci-Heaps. Man kann zeigen, dass der Algorithmus von Prim damit im Wesentlichen bestmöglich ist, da man mit seiner Hilfe auch Zahlen sortieren kann.

Anwendungen

Die Berechnung minimaler Spannbäume findet direkte Anwendungen in der Praxis, wenn man zum Beispiel kostengünstig zusammenhängende Netzwerke (z.B. Telefonnetzwerke, elektrische Netzwerke u.a.) herstellen will. Auch bei Computernetzwerken mit redundanten Pfaden werden zur Vermeidung von Paketverdopplungen Spannbäume genutzt (siehe Spanning Tree Protocol).

In der Graphentheorie selbst sind MST-Algorithmen häufig Grundlage komplexerer Algorithmen für schwierigere Probleme. Die Berechnung minimaler Spannbäume ist zum Beispiel Bestandteil von Approximationsalgorithmen für das Steinerbaum-Problem oder für das Problem des Handlungsreisenden, oft auch Traveling-Salesman-Problem genannt (siehe MST-Heuristik).

Literatur

• Otakar Boruvka on Minimum Spanning Tree Problem (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová
• A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Bernard Chazelle, 1999

Weblinks

• Minimal spannende Bäume, Ronny Harbich, 2006
• Minimal aufspannende Bäume, Algorithmus der Woche 21, 2006

Siehe auch

• MST-Heuristik für das Handlungsreisenden-Problem (Traveling Salesperson Problem)
• Spanning Tree Protocol

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Spannbaum, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.