imported>Invisigoth67: form

2025-07-19T15:07:37Z

form

Neue Seite

[[Datei:Spanning Trees qtl1.svg|mini|Alle 16 Spannbäume des [[Vollständiger Graph|vollständigen Graphen]] mit 4 Knoten]]
[[Datei:Minimum spanning tree.svg|mini|Ein Graph mit einem minimalen Spannbaum]]
[[Datei:Натурализация гамильтоновых циклов.jpg|mini|Drei Beispiele für Spannbäume auf einem 8x8 [[Gittergraph]]]]

Ein '''Spannbaum''' (auch ''aufspannender Baum'' oder ''Gerüst'' genannt; englisch ''spanning tree'', manchmal [[Falscher Freund|fälschlich]] als „spannender Baum“ übersetzt) ist in der [[Graphentheorie]] ein [[Teilgraph]] eines [[Ungerichteter Graph|ungerichteten Graphen]], der ein [[Baum (Graphentheorie)|Baum]] ist und alle Knoten dieses Graphen enthält.<ref>Ein vergleichbares Problem auf [[Gerichteter Graph|gerichteten Graphen]] ist das Finden eines Teilgraphen, der ein [[gewurzelter Baum]] ist.</ref> Spannbäume existieren nur in [[Zusammenhang von Graphen|zusammenhängenden]] Graphen.

In einem [[Vollständiger Graph|vollständigen Graphen]] <math>K_n</math> findet man nach der [[Cayley-Formel]] <math>n^{n-2}</math> verschiedene Spannbäume. Im nebenstehenden Beispiel des <math>K_4</math> sind es <math>4^{4-2}=16</math> Stück.

== Unterarten ==
Ein Teilgraph, der in einem Graphen für jede [[Zusammenhang von Graphen|Komponente]] einen Spannbaum ergibt, wird ''Gerüst'', ''Spannwald'' oder ''aufspannender [[Wald (Graphentheorie)|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 [[Kantengewichteter Graph|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 <math>k</math>-Spanner eines Graphen ist ein aufspannender Teilgraph, in dem die [[Abstand (Graphentheorie)|Distanz]] jedes Knotenpaares höchstens dem <math>k</math>-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 [[Graph (Graphentheorie)|Graphen]] <math>G=(V,E)</math> mit Knotenmenge <math>V</math> und Kantenmenge <math>E</math> mittels [[Breitensuche|Breiten-]] oder [[Tiefensuche]] in <math>\mathcal{O} \bigl( \left| V \right| + \left| E \right| \bigr)</math> 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 <math>E</math> 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 <math>O(\log n)</math> Zeit zu lösen<ref>{{cite journal
| last1 = Chong
| first1 = Ka Wong
| last2 = Han
| first2 = Yijie
| last3 = Lam
| first3 = Tak Wah
| doi = 10.1145/375827.375847
| issue = 2
| journal = Journal of the Association for Computing Machinery
| pages = 297–323
| title = Concurrent threads and optimal parallel minimum spanning trees algorithm
| volume = 48
| year = 2001
| language = en }}</ref><ref>{{cite journal
| last1 = Pettie | first1 = Seth
| last2 = Ramachandran | first2 = Vijaya
| doi = 10.1137/S0097539700371065
| issue = 6
| journal = SIAM Journal on Computing
| pages = 1879–1895
| title = A randomized time-work optimal parallel algorithm for finding a minimum spanning forest
| volume = 31
| year = 2002 |language=en |url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf
}}</ref>. Bader und Cong präsentieren einen Algorithmus, der minimale Spannbäume fünffach schneller auf acht Prozessoren berechnet als ein optimierter sequentieller Algorithmus<ref>{{cite journal
| last1 = Bader
| first1 = David A.
| last2 = Cong
| first2 = Guojing
| doi = 10.1016/j.jpdc.2006.06.001
| issue = 11
| journal = Journal of Parallel and Distributed Computing
| pages = 1366–1378
| title = Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs
| volume = 66
| year = 2006
| language = en }}</ref>.

Weitere spezialisierte Algorithmen wurden für minimale Spannbäume im [[External Memory Minimaler Spannbaum|External-Memory-Modell]] entwickelt.<ref>{{Literatur |Autor=Roman Dementiev, Peter Sanders, Dominik Schultes, Jop Sibeyn |Titel=Engineering an External Memory Minimum Spanning Tree Algorithm |Sammelwerk=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 |Reihe=IFIP International Federation for Information Processing |BandReihe=155 |Verlag=Springer |Datum=2004 |DOI=10.1007/1-4020-8141-3_17}}</ref> Laut den Autoren arbeitet dieser Algorithmus nur 2–5 mal langsamer als ein Algorithmus, der nur auf dem Hauptspeicher arbeitet.

Ein Spannbaum eines [[Graph (Graphentheorie)|Graphen]] kann in linearer Zeit entweder durch [[Tiefensuche]] oder durch [[Breitensuche]] gefunden werden. Beide [[Algorithmus|Algorithmen]] untersuchen den gegebenen Graphen ausgehend von einem beliebigen [[Knoten (Graphentheorie)|Knoten]], indem sie die [[Nachbar (Graphentheorie)|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 (Datenstruktur)|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 [[Graphsuchalgorithmus|Graphsuchsalgorithmus]] bekannt.<ref>{{Literatur |Autor=Dexter Kozen |Titel=The Design and Analysis of Algorithms |Verlag=Monographs in Computer Science |Datum=1992 |ISBN=978-0-387-97687-7 |Seiten=19}}</ref>

Spannbäume sind wichtig für [[Parallelrechner]] und [[Verteiltes System|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 [[Computer]]n sind jedoch für Parallelrechner und verteilte Systeme nicht gut geeignet.<ref>{{cite journal|last=Reif|first=John H.|authorlink=John Reif|doi=10.1016/0020-0190(85)90024-9|issue=5|journal=Information Processing Letters|pages=229–234|title=Depth-first search is inherently sequential|volume=20|year=1985 |language=en}}.</ref> Stattdessen haben Forscher mehrere spezialisiertere Algorithmen entwickelt, um Spannbäume in diesen Berechnungsmodellen zu finden.<ref>{{cite journal|last1=Gallager|first1=R. G.|last2=Humblet|first2=P. A.|last3=Spira|first3=P. M.|doi=10.1145/357195.357200|issue=1|journal=ACM Transactions on Programming Languages and Systems|pages=66–77|title=A distributed algorithm for minimum-weight spanning trees|volume=5|year=1983 |language=en}}; {{cite journal|last=Gazit|first=Hillel|doi=10.1137/0220066|issue=6|journal=SIAM Journal on Computing|pages=1046–1067|title=An optimal randomized parallel algorithm for finding connected components in a graph|volume=20|year=1991 |language=en}}; {{cite journal|last1=Bader|first1=David A.|last2=Cong|first2=Guojing|doi=10.1016/j.jpdc.2005.03.011|issue=9|journal=Journal of Parallel and Distributed Computing|pages=994–1006|title=A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)|url=http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf |volume=65 |year=2005 |language=en |accessdate=2020-04-13 |archiveurl=https://web.archive.org/web/20150923201604/http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf| archivedate=2015-09-23}}.</ref>

Optimale Spannbäume wurden auch für endliche Punktmengen in einem geometrischen [[Raum (Mathematik)|Raum]] wie der [[Euklidischer Raum|euklidischen]] [[Ebene (Mathematik)|Ebene]] untersucht. Für eine solche Eingabe ist ein Spannbaum wieder ein [[Baum (Graphentheorie)|Baum]], dessen [[Knoten (Graphentheorie)|Knoten]] die angegebenen [[Punkt (Geometrie)|Punkte]] sind. Die Qualität des Baums wird auf die gleiche Weise wie in einem Graphen gemessen, wobei der [[Euklidischer Abstand|euklidische Abstand]] zwischen Punktpaaren als Gewicht für jede [[Kante (Graphentheorie)|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 (Informatik)|Laufzeit]] in der Größenordnung <math>O(n \cdot \log n)</math> gelöst werden, indem die [[Delaunay-Triangulierung]] erstellt und anschließend ein [[Algorithmus]] mit linearer Laufzeit für den minimalen Spannbaum eines [[Planarer Graph|planaren Graphen]] auf die resultierende Triangulierung angewendet wird.<ref>{{cite journal |last=Eppstein |first=David |authorlink=David Eppstein |title=Spanning trees and spanners |journal=Handbook of Computational Geometry |publisher=Elsevier |year=1999 |pages=425–461 |language=en |url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf}}</ref>

== Anwendungen ==
[[Datei:MAZE 30x20 Prim.ogv|mini|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. 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 [[Rechnernetz]]en 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 [[Approximationsalgorithmus|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 [[Labyrinth]]en 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 ==
* 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]]: ''[http://www.cs.princeton.edu/~chazelle/pubs/mst.pdf A minimum spanning tree algorithm with inverse-Ackermann type complexity] (PDF; 321 kB)''. Journal ACM 47 (2000), Seiten 1028–1047.

== Weblinks ==
{{Wikiversity|Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 18|Eine Vorlesung über Spannbäume im Rahmen eines Kurses zur diskreten Mathematik}}
* Katharina Langkau, Martin Skutella: [http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo21.php Minimal aufspannende Bäume], Algorithmus der Woche, 25. Juli 2006. Fakultätentag Informatik.

== Anmerkungen ==
<references />

{{Normdaten|TYP=s|GND=4761178-9}}

[[Kategorie:Bäume und Wälder]]
[[Kategorie:Wikipedia:Artikel mit Video]]

Spannbaum - Versionsgeschichte

imported>Invisigoth67: form