Spannbaum

aus Wikipedia, der freien Enzyklopädie
Alle 16 Spannbäume des vollständigen Graphen mit 4 Knoten
Datei:Minimum spanning tree.svg
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.

In einem vollständigen Graphen findet man nach der Cayley-Formel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n^{n-2}} verschiedene Spannbäume. Im nebenstehenden Beispiel des Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_4} sind es Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 4^{4-2}=16} Stück.

Unterarten

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -Spanner eines Graphen ist ein aufspannender Teilgraph, in dem die Distanz jedes Knotenpaares höchstens dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -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 Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(V,E)} mit Knotenmenge und Kantenmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E} mittels Breiten- oder Tiefensuche in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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]

Anwendungen

Datei:MAZE 30x20 Prim.ogv
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

Weblinks

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

Anmerkungen

  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..
  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, Nr. 5, 1985, S. 229–234. doi:10.1016/0020-0190(85)90024-9..
  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, Nr. 1, 1983, S. 66–77. doi:10.1145/357195.357200.; Hillel Gazit: An optimal randomized parallel algorithm for finding connected components in a graph. In: SIAM Journal on Computing. 20, Nr. 6, 1991, S. 1046–1067. doi:10.1137/0220066.; David A. Bader, Guojing Cong: A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs). In: Journal of Parallel and Distributed Computing. 65, Nr. 9, 2005, S. 994–1006. doi:10.1016/j.jpdc.2005.03.011..
  9. ↑ David Eppstein: Handbook of Computational Geometry. In: Elsevier (Hrsg.): Spanning trees and spanners. 1999, S. 425–461.
Abgerufen von „https://de.wikiup.org/index.php?title=Spannbaum&oldid=203332541“