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.

In einem vollständigen Graphen K n {\displaystyle K_{n}} findet man nach der Cayley-Formel n n − 2 {\displaystyle n^{n-2}} verschiedene Spannbäume. Im nebenstehenden Beispiel des K 4 {\displaystyle K_{4}} sind es 4 4 − 2 = 16 {\displaystyle 4^{4-2}=16} Stück.

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 oder Gerüst kleinsten Wertes. Ist die Kantengewichtungsfunktion injektiv, so ist der minimale Spannbaum eindeutig.

Ein k {\displaystyle k} -Spanner eines Graphen ist ein aufspannender Teilgraph, in dem die Distanz jedes Knotenpaares höchstens dem k {\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 einem Graphen G = ( V , E ) {\displaystyle G=(V,E)} mit Knotenmenge V {\displaystyle V} und Kantenmenge E {\displaystyle E} mittels Breiten- oder Tiefensuche in O ( | V | + | E | ) {\displaystyle {\mathcal {O}}{\bigl (}\left|V\right|+\left|E\right|{\bigr )}} gefunden werden.

Zur effizienten Berechnung minimaler Spannbäume existiert 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 E {\displaystyle E} hin zu einem 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 O ( log ⁡ n ) {\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 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.

Ein Spannbaum eines Graphen kann in linearer Zeit entweder durch Tiefensuche oder durch Breitensuche gefunden werden. Beide Algorithmen untersuchen den gegebenen Graphen ausgehend von einem beliebigen Knoten, indem sie die Nachbarn der von ihnen gefundenen Knoten durchlaufen und jeden nicht gefundenen Nachbarn zu einer Datenstruktur hinzufügen, die später untersucht werden soll. Sie unterscheiden sich darin, ob es sich bei dieser Datenstruktur um einen Stapelspeicher (bei der Tiefensuche) oder eine Warteschlange (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 verwendeten Graphsuchsalgorithmus bekannt.^[6]

Spannbäume sind wichtig für Parallelrechner und verteilte Systeme, um die Kommunikation zwischen einer Reihe von Prozessoren aufrechtzuerhalten. Siehe zum Beispiel das Spanning Tree Protocol oder das Shout Protocol für verteilte Systeme. Die Tiefensuche und Breitensuche zum Erstellen von Spannbäumen auf sequentiellen Computern 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 geometrischen Raum wie der euklidischen Ebene untersucht. Für eine solche Eingabe ist ein Spannbaum wieder ein Baum, dessen Knoten die angegebenen Punkte sind. Die Qualität des Baums wird auf die gleiche Weise wie in einem Graphen gemessen, wobei der euklidische Abstand zwischen Punktpaaren als Gewicht für jede Kante 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 das Optimierungsproblem zu lösen. Das Problem des euklidischen minimalen Spannbaums kann beispielsweise effizienter mit einer Laufzeit in der Größenordnung O ( n ⋅ log ⁡ n ) {\displaystyle O(n\cdot \log n)} gelöst werden, indem die Delaunay-Triangulierung erstellt und anschließend ein Algorithmus mit linearer Laufzeit für den minimalen Spannbaum eines planaren 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. Ein Telefon- oder Netzbetreiber möchte z. B. Städte verbinden und dabei möglichst wenig Geld für z. B. Kabel ausgeben. Auch bei Rechnernetzen mit redundanten Pfaden werden zur Vermeidung von durch einen Broadcast entstandenen 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.

• 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 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. 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 des Originals vom 23. September 2015 im Internet 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]).