EinSpannbaum (auchaufspannender Baum oderGerüst genannt; englischspanning tree, manchmalfälschlich als „spannender Baum“ übersetzt) ist in derGraphentheorie einTeilgraph einesungerichteten Graphen, der einBaum ist und alle Knoten dieses Graphen enthält.^[1] Spannbäume existieren nur inzusammenhängenden Graphen.

In einemvollständigen Graphen${\displaystyle K_n}$ findet man nach derCayley-Formel${\displaystyle n^{n-2}}$ verschiedene Spannbäume. Im nebenstehenden Beispiel des${\displaystyle K_4}$ sind es${\displaystyle 4^{4-2}=16}$ Stück.

Ein Teilgraph, der in einem Graphen für jedeKomponente einen Spannbaum ergibt, wirdGerüst,Spannwald oderaufspannenderWald genannt. Dabei muss der Graph nicht notwendigerweise zusammenhängend sein. In zusammenhängenden Graphen sindGerüst undSpannbaum identische Begriffe, während Spannbäume für unzusammenhängende Graphen per Definition nicht existieren.

Inkantengewichteten Graphen lässt sich als Gewicht eines Graphen die Summe seiner Kantengewichte definieren. Ein Spannbaum bzw. ein Gerüst heißtminimal, wenn kein anderer Spannbaum bzw. kein anderes Gerüst in demselben Graphen mit geringerem Gewicht existiert. Häufig wirdminimaler Spannbaum auch mitMST (Abkürzung des englischen BegriffsMinimum Spanning Tree) oderMCST (Minimum Cost Spanning Tree – ein Spannbaum mit minimalen Kosten) abgekürzt. Stattminimales Gerüst sagt man auchMinimalgerüst oderGerüst kleinsten Wertes. Ist die Kantengewichtungsfunktion injektiv, so ist der minimale Spannbaum eindeutig.

Ein${\displaystyle k}$-Spanner eines Graphen ist ein aufspannender Teilgraph, in dem dieDistanz jedes Knotenpaares höchstens dem${\displaystyle k}$-fachen seiner Distanz im Ausgangsgraphen entspricht.

Bei einem gradbeschränkten Spannbaum dürfen nicht beliebig viele Kanten an einem Knoten zusammenlaufen.

Ein nicht minimaler Spannbaum kann in einemGraphen${\displaystyle G=(V,E)}$ mit Knotenmenge${\displaystyle V}$ und Kantenmenge${\displaystyle E}$ mittelsBreiten- oderTiefensuche in${\displaystyle \mathcal{O}(\left|V\right|+\left|E\right|)}$ gefunden werden.

Zur effizienten Berechnung minimaler Spannbäume existiert eine Vielzahl von sequentiellen Algorithmen, zum Beispiel derAlgorithmus von Prim, derAlgorithmus von Kruskal und derAlgorithmus von Borůvka. Alle drei genannten Algorithmen vergrößern iterativ eine Teilmenge der Kanten${\displaystyle E}$ hin zu einem minimalen Spannbaum und bieten dabei unterschiedliche Ansätze zur parallelen Berechnung. Ein anderes Verfahren ist derAlgorithmus 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${\displaystyle O(\log n)}$ 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 imExternal-Memory-Modell entwickelt.^[5] Laut den Autoren arbeitet dieser Algorithmus nur 2–5 mal langsamer als ein Algorithmus, der nur auf dem Hauptspeicher arbeitet.

Ein Spannbaum einesGraphen kann in linearer Zeit entweder durchTiefensuche oder durchBreitensuche gefunden werden. BeideAlgorithmen untersuchen den gegebenen Graphen ausgehend von einem beliebigenKnoten, indem sie dieNachbarn der von ihnen gefundenen Knoten durchlaufen und jeden nicht gefundenen Nachbarn zu einerDatenstruktur hinzufügen, die später untersucht werden soll. Sie unterscheiden sich darin, ob es sich bei dieser Datenstruktur um einenStapelspeicher (bei der Tiefensuche) oder eineWarteschlange (bei der Breitensuche) handelt. In beiden Fällen kann ein Spannbaum gebildet werden, indem jeder andere Knoten als der Wurzelknoten mit dem Knoten verbunden wird, von dem aus er gefunden wurde. Dieser Baum ist als Tiefensuchbaum oder Breitensuchbaum gemäß dem zur Erstellung verwendetenGraphsuchsalgorithmus bekannt.^[6]

Spannbäume sind wichtig fürParallelrechner undverteilte Systeme, um die Kommunikation zwischen einer Reihe von Prozessoren aufrechtzuerhalten. Siehe zum Beispiel dasSpanning Tree Protocol oder das Shout Protocol für verteilte Systeme. DieTiefensuche undBreitensuche zum Erstellen von Spannbäumen auf sequentiellenComputern sind jedoch für Parallelrechner und verteilte Systeme nicht gut geeignet.^[7] Stattdessen haben Forscher mehrere spezialisiertere Algorithmen entwickelt, um Spannbäume in diesen Berechnungsmodellen zu finden.^[8]

Optimale Spannbäume wurden auch für endliche Punktmengen in einem geometrischenRaum wie dereuklidischenEbene untersucht. Für eine solche Eingabe ist ein Spannbaum wieder einBaum, dessenKnoten die angegebenenPunkte sind. Die Qualität des Baums wird auf die gleiche Weise wie in einem Graphen gemessen, wobei dereuklidische Abstand zwischen Punktpaaren als Gewicht für jedeKante verwendet wird. So entspricht beispielsweise ein euklidischer minimaler Spannbaum einem minimalen Spannbaum in einem vollständigen Graphen mit euklidischen Kantengewichten. Es ist jedoch nicht erforderlich, diesen Graphen zu erstellen, um dasOptimierungsproblem zu lösen. Das Problem des euklidischen minimalen Spannbaums kann beispielsweise effizienter mit einerLaufzeit in der Größenordnung${\displaystyle O(n\cdot \log n)}$ gelöst werden, indem dieDelaunay-Triangulierung erstellt und anschließend einAlgorithmus mit linearer Laufzeit für den minimalen Spannbaum einesplanaren Graphen auf die resultierende Triangulierung angewendet wird.^[9]

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 beiRechnernetzen mit redundanten Pfaden werden zur Vermeidung von Paketverdopplungen Spannbäume genutzt (sieheSpanning 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 vonApproximationsalgorithmen für dasProblem des Handlungsreisenden, oft auch in der englischen Bezeichnungtravelling salesman problem (TSP) genannt (sieheMST-Heuristik), oder für dasSteinerbaumproblem. Letzteres ist auch eine Verallgemeinerung des Problems, einen minimalen Spannbaum zu finden.

Des Weiteren spielen Spannbäume bei der algorithmischen Erzeugung vonLabyrinthen 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.

• Jaroslav Nesetril, Eva Milková, Helena Nesetrilová:Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history, Discrete Mathematics, 233 (2001), Seiten 3–36.
• Bernard Chazelle:A minimum spanning tree algorithm with inverse-Ackermann type complexity (PDF; 321 kB). Journal ACM 47 (2000), Seiten 1028–1047.

Wikiversity: Eine Vorlesung über Spannbäume im Rahmen eines Kurses zur diskreten Mathematik – Kursmaterialien

• Katharina Langkau, Martin Skutella:Minimal aufspannende Bäume, Algorithmus der Woche, 25. Juli 2006. Fakultätentag Informatik.

1. ↑Ein vergleichbares Problem aufgerichteten Graphen ist das Finden eines Teilgraphen, der eingewurzelter 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. Jahrgang,Nr. 2, 2001,S. 297–323,doi:10.1145/375827.375847 (englisch). 
3. ↑Seth Pettie, Vijaya Ramachandran:A randomized time-work optimal parallel algorithm for finding a minimum spanning forest. In:SIAM Journal on Computing. 31. Jahrgang,Nr. 6, 2002,S. 1879–1895,doi:10.1137/S0097539700371065 (englisch,umich.edu [PDF]). 
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. Jahrgang,Nr. 11, 2006,S. 1366–1378,doi:10.1016/j.jpdc.2006.06.001 (englisch). 
5. ↑Roman Dementiev, Peter Sanders, Dominik Schultes, Jop Sibeyn:Engineering an External Memory Minimum Spanning Tree Algorithm. In:Exploring New Frontiers of Theoretical Informatics – IFIP 18th World Computer Congress TC1 3rd International Conference on Theoretical Computer Science (TCS2004) 22–27 August 2004 Toulouse, France (= IFIP International Federation for Information Processing.Band 155). Springer, 2004,doi:10.1007/1-4020-8141-3_17. 
6. ↑Dexter Kozen:The Design and Analysis of Algorithms. Monographs in Computer Science, 1992,ISBN 978-0-387-97687-7,S. 19. 
7. ↑John H. Reif:Depth-first search is inherently sequential. In:Information Processing Letters. 20. Jahrgang,Nr. 5, 1985,S. 229–234,doi:10.1016/0020-0190(85)90024-9 (englisch). .
8. ↑R. G. Gallager, P. A. Humblet, P. M. Spira:A distributed algorithm for minimum-weight spanning trees. In:ACM Transactions on Programming Languages and Systems. 5. Jahrgang,Nr. 1, 1983,S. 66–77,doi:10.1145/357195.357200 (englisch). ; Hillel Gazit:An optimal randomized parallel algorithm for finding connected components in a graph. In:SIAM Journal on Computing. 20. Jahrgang,Nr. 6, 1991,S. 1046–1067,doi:10.1137/0220066 (englisch). ; David A. Bader, Guojing Cong:A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs). In:Journal of Parallel and Distributed Computing. 65. Jahrgang,Nr. 9, 2005,S. 994–1006,doi:10.1016/j.jpdc.2005.03.011 (englisch,cc.gatech.edu (Memento desOriginals vom 23. September 2015 imInternet Archive) [abgerufen am 13. April 2020]). .
9. ↑David Eppstein:Spanning trees and spanners. In:Handbook of Computational Geometry. Elsevier, 1999,S. 425–461 (englisch,uci.edu [PDF]). 

• Bäume und Wälder

• Wikipedia:Artikel mit Video