Spannbaum

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Minimaler Spannbaum)
Zur Navigation springen Zur Suche springen
Alle 16 Spannbäume des vollständigen Graphen mit 4 Knoten
Ein Graph mit einem minimalen 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Ein nicht minimaler Spannbaum kann in einem Graphen mit Knotenmenge und Kantenmenge mittels Breiten- oder Tiefensuche in gefunden werden.

Zur effizienten Berechnung minimaler Spannbäume existieren eine Vielzahl von sequentiellen Algorithmen, zum Beispiel der Algorithmus von Prim, der Algorithmus von Kruskal und der Algorithmus von Borůvka. Alle drei genannten Algorithmen vergrößern iterativ eine Teilmenge der Kanten hin zu einen minimalen Spannbaum und bieten dabei unterschiedliche Ansätze zur parallelen Berechnung. Ein anderes Verfahren ist der Algorithmus von Chazelle.

Neben den oben genannten Algorithmen gibt es viele weitere Veröffentlichungen zur parallelen Berechnung minimaler Spannbäume. Mit einer linearen Anzahl an Prozessoren ist es möglich, das Problem in Zeit zu lösen[2][3]. Bader und Cong präsentieren einen Algorithmus, der minimale Spannbäume fünffach schneller auf acht Prozessoren berechnet als ein optimierter sequentieller Algorithmus[4].

Weitere spezialisierte Algorithmen wurden für minimale Spannbäume im External Memory Modell entwickelt[5]. Laut den Autoren arbeitet dieser Algorithmus nur 2–5 mal langsamer als ein Algorithmus, der nur auf dem Hauptspeicher arbeitet.

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus von Prim generiert ein Labyrinth.

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 (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 Problem des Handlungsreisenden, oft auch in der englischen Bezeichnung travelling salesman problem (TSP) genannt (siehe MST-Heuristik), 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.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  1. Ein vergleichbares Problem auf gerichteten Graphen ist das Finden eines Teilgraphen, der ein gewurzelter Baum ist.
  2. Ka Wong Chong, Yijie Han, Tak Wah Lam: Concurrent threads and optimal parallel minimum spanning trees algorithm. In: Journal of the Association for Computing Machinery. 48, Nr. 2, 2001, S. 297–323. doi:10.1145/375827.375847.
  3. Seth Pettie, Vijaya Ramachandran: A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. In: SIAM Journal on Computing. 31, Nr. 6, 2002, S. 1879–1895. doi:10.1137/S0097539700371065.
  4. David A. Bader, Guojing Cong: Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. In: Journal of Parallel and Distributed Computing. 66, Nr. 11, 2006, S. 1366–1378. doi:10.1016/j.jpdc.2006.06.001.
  5. Roman Dementiev, Peter Sanders, Dominik Schultes, Jop F. Sibeyn: Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) 2004, S. 195–208..