Wikipedia · einfach zusammengefasst · Stand
Spannbaum
Ein Spannbaum eines Graphen kann in linearer Zeit entweder durch Tiefensuche oder durch Breitensuche gefunden werden. Beide Algorithmen untersuchen den …
Inhalt4 Abschnitte
Grundidee und Voraussetzungen
Ein Spannbaum, auch aufspannender Baum oder Gerüst, ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen. Er ist ein Baum, enthält also keine Zyklen, und enthält zugleich alle Knoten des ursprünglichen Graphen. Spannbäume existieren nur bei zusammenhängenden Graphen.
Für den vollständigen Graphen Kₙ gibt die Cayley-Formel die Anzahl verschiedener Spannbäume an: n^(n−2). Für K₄ gibt es daher 4^(4−2) = 16 Spannbäume.
Verwandte Formen und minimale Spannbäume
Ein Spannwald, auch Gerüst oder aufspannender Wald, enthält für jede Zusammenhangskomponente eines Graphen einen Spannbaum. Deshalb kann ein Spannwald auch für einen nicht zusammenhängenden Graphen gebildet werden. In einem zusammenhängenden Graphen sind Gerüst und Spannbaum identisch; für unzusammenhängende Graphen existiert dagegen per Definition kein Spannbaum.
In einem kantengewichteten Graphen ist das Gewicht eines Graphen die Summe seiner Kantengewichte. Ein minimaler Spannbaum ist ein Spannbaum, für den kein anderer Spannbaum desselben Graphen ein geringeres Gewicht besitzt. Übliche Abkürzungen sind MST (Minimum Spanning Tree) und MCST (Minimum Cost Spanning Tree). Bei einem Gerüst spricht man auch von Minimalgerüst oder einem Gerüst kleinsten Wertes. Ist die Kantengewichtungsfunktion injektiv, also haben keine zwei Kanten dasselbe Gewicht, dann ist der minimale Spannbaum eindeutig.
Ein k-Spanner ist ein aufspannender Teilgraph, in dem die Distanz jedes Knotenpaares höchstens das k-Fache seiner Distanz im ursprünglichen Graphen beträgt. Bei einem gradbeschränkten Spannbaum ist außerdem begrenzt, wie viele Kanten an einem Knoten zusammenlaufen dürfen.
Berechnung von Spannbäumen
Für einen Graphen G = (V,E) kann ein nicht minimaler Spannbaum mit Breiten- oder Tiefensuche in O(|V| + |E|) gefunden werden. Beide Verfahren starten bei einem beliebigen Knoten und untersuchen schrittweise Nachbarn bereits gefundener Knoten. Jeder neu gefundene Knoten wird mit dem Knoten verbunden, von dem aus er entdeckt wurde; dieser Startknoten ist die Wurzel des entstehenden Baums.
Der Unterschied liegt in der Datenstruktur für noch zu untersuchende Knoten: Die Tiefensuche verwendet einen Stapelspeicher, die Breitensuche eine Warteschlange. Die resultierenden Bäume heißen entsprechend Tiefensuchbaum beziehungsweise Breitensuchbaum.
Minimale Spannbäume lassen sich unter anderem mit den Algorithmen von Prim, Kruskal und Borůvka berechnen. Sie erweitern jeweils iterativ eine Teilmenge der Kanten E zu einem minimalen Spannbaum, unterscheiden sich jedoch in ihren Ansätzen zur parallelen Berechnung. Ein weiteres Verfahren ist der Algorithmus von Chazelle. Mit einer linearen Anzahl von Prozessoren kann das Problem in O(log n) Zeit gelöst werden. Bader und Cong beschreiben einen Algorithmus, der auf acht Prozessoren minimale Spannbäume fünffach schneller berechnet als ein optimierter sequentieller Algorithmus. Für das External-Memory-Modell gibt es spezialisierte Verfahren, die laut ihren Autoren nur 2–5-mal langsamer als Algorithmen sind, die ausschließlich im Hauptspeicher arbeiten.
Für Parallelrechner und verteilte Systeme sind die gewöhnliche Tiefen- und Breitensuche nicht gut geeignet; dafür wurden spezialisierte Algorithmen entwickelt. Bei endlichen Punktmengen in einem geometrischen Raum werden Punktabstände als Kantengewichte verwendet. Ein euklidischer minimaler Spannbaum entspricht damit einem minimalen Spannbaum eines vollständigen Graphen mit euklidischen Kantengewichten. Der vollständige Graph muss aber nicht erzeugt werden: In der euklidischen Ebene kann zunächst eine Delaunay-Triangulierung gebildet und darauf ein linearer MST-Algorithmus für planare Graphen angewendet werden. Die Laufzeit liegt dann in der Größenordnung O(n · log n).
Praktische Anwendungen
Minimale Spannbäume helfen, kostengünstige zusammenhängende Netzwerke zu planen, etwa Telefonnetze oder elektrische Netze. Städte können so verbunden werden, dass beispielsweise möglichst wenig Kabelkosten entstehen. In Rechnernetzen mit redundanten Wegen verhindern Spannbäume durch das Spanning Tree Protocol Paketverdopplungen, die durch Broadcasts entstehen können.
MST-Algorithmen sind außerdem Bausteine komplexerer Algorithmen, etwa von Approximationsalgorithmen für das Problem des Handlungsreisenden (travelling salesman problem, TSP; MST-Heuristik) und für das Steinerbaumproblem. Das Steinerbaumproblem verallgemeinert die Suche nach einem minimalen Spannbaum.
Bei der algorithmischen Erzeugung von Labyrinthen steht ein Knoten des Spannbaums für ein Feld und eine Kante für einen möglichen Übergang zu einem Nachbarfeld. Eine fehlende Kante entspricht einer Wand. Weil jeder Spannbaum zyklenfrei ist, besitzt ein auf diese Weise erzeugtes Labyrinth stets genau einen Lösungsweg.
