Spannbaum
Ein Spannbaum (auch aufspannender Baum oder Gerüst genannt; englisch spanning tree, manchmal fälschlich als „spannender Baum“ übersetzt) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten dieses Graphen enthält.[1] Spannbäume existieren nur in zusammenhängenden Graphen.
Unterarten
Ein Teilgraph, der in einem Graphen für jede Komponente einen Spannbaum ergibt, wird Gerüst, Spannwald oder aufspannender Wald genannt. Dabei muss der Graph nicht notwendigerweise zusammenhängend sein. In zusammenhängenden Graphen sind Gerüst und Spannbaum identische Begriffe, während Spannbäume für unzusammenhängende Graphen per Definition nicht existieren.
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 wird minimaler Spannbaum auch mit MST (Abkürzung des englischen Begriffs Minimum Spanning Tree) oder MCST (Minimum Cost Spanning Tree – ein Spannbaum mit minimalen Kosten) abgekürzt. Statt minimales Gerüst sagt man auch Minimalgerüst. Ist die Kantengewichtungsfunktion injektiv, so ist der minimale Spannbaum eindeutig.
Ein 
-Spanner
eines Graphen ist ein aufspannender Teilgraph, in dem die Distanz
jedes Knotenpaares höchstens dem -fachen
seiner Distanz im Ausgangsgraphen entspricht.
Bei einem gradbeschränkten Spannbaum dürfen nicht beliebig viele Kanten an einem Knoten zusammenlaufen.
Algorithmen
Ein nicht minimaler Spannbaum kann in einem Graphen 
mit Knotenmenge 
und Kantenmenge 
mittels Breiten-
oder Tiefensuche in 
gefunden werden.
Bekannte Verfahren zum Finden eines minimalen Spannbaumes sind u.a. der Algorithmus von Borůvka, der Algorithmus von Jarník/Prim/Dijkstra, der Algorithmus von Kruskal und der Algorithmus von Chazelle.
Anwendungen
Die Berechnung minimaler Spannbäume findet direkte Anwendung in der Praxis, beispielsweise für die Erstellung von kostengünstigen zusammenhängenden Netzwerken, wie beispielsweise Telefonnetze oder elektrische Netze. Auch bei Rechnernetzen mit redundanten Pfaden werden zur Vermeidung von Paketverdopplungen Spannbäume genutzt.
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 Problem des Handlungsreisenden, oft auch in der englischen Bezeichnung travelling salesman problem (TSP) genannt, oder für das Steinerbaumproblem. Letzteres ist auch eine Verallgemeinerung des Problems, einen minimalen Spannbaum zu finden.
Des Weiteren spielen Spannbäume bei der algorithmischen Erzeugung von Labyrinthen eine Rolle. Ein Knoten im Spannbaum entspricht dabei einem Feld, während eine Kante einen möglichen Übergang zu einem Nachbarfeld darstellt. Eine fehlende Kante beschreibt folglich eine Wand. Da Spannbäume wie alle Bäume zyklenfrei sind, besitzt ein mittels Spannbäumen erzeugtes Labyrinth stets nur einen einzigen Lösungsweg.
Anmerkungen
- ↑ Ein vergleichbares Problem auf gerichteten Graphen ist das Finden eines Teilgraphen, der ein gewurzelter Baum ist.
Wikipedia.de
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 28.05. 2021