Spannender Baum

Ein spannender Baum (synonym auch Spannbaum oder aufspannender Baum) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle seine Knoten enthält. Spannende Bäume existieren somit nur in zusammenhängenden Graphen.

Einen Teilgraphen, der in nicht notwendigerweise zusammenhängenden Graphen für jede Komponente ein spannenden Baum ergibt nennt man Gerüst. In zusammenhängenden Graphen sind Gerüst und spannender Baum also identische Begriffe, während spannende Bäume für unzusammenhängende Graphen nicht definiert sind.

In kantengewichteten Graphen lässt sich als Gewicht eines spannenden Graphen die Summe seiner Kantengewichte definieren. Ein spannender Baum bzw. ein Gerüst heißt minimal, wenn kein anderer spannender Baum bzw. kein anderes Gerüst in dem selben Graphen mit geringerem Gewicht existiert. Häufig kürzt man minimal spannender Baum auch mit MST (Abk. des englischen Begriffs Minimum Spanning Tree) ab. Statt minimales Gerüst sagt man auch Minimalgerüst.

Minimal spannende Bäume lassen sich mit dem Kruskal-Algorithmus oder dem Algorithmus von Prim bestimmen, wobei die Laufzeit bei einfacher Implementierung durch

Das Spannbaumproblem tritt in der Praxis beispielsweise bei der kürzesten Verdrahtung von Kommunikationsnetzen auf. Auch für Approximationsalgorithmen für das Problem des Handlungsreisenden lassen sich minimale Spannbäume verwenden.

Näheres siehe unter Wälder und Bäume in der Graphentheorie.

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