Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 2. Juni 2020 

Minimal spannender Baum


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Ein spannender Baum (synonym auch Spannbaum oder aufspannender Baum ) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen der ein Baum ist und alle seine Knoten enthält. Bäume existieren somit nur in zusammenhängenden Graphen.

Einen Teilgraphen der in nicht notwendigerweise Graphen für jede Komponente ein spannenden Baum ergibt nennt man Gerüst . In zusammenhängenden Graphen sind Gerüst und spannender Baum also identische Begriffe während spannende Bäume unzusammenhängende Graphen nicht definiert sind.

In kantengewichteten Graphen lässt sich als Gewicht eines Graphen die Summe seiner Kantengewichte definieren. Ein Baum bzw. ein Gerüst heißt minimal wenn kein anderer spannender Baum bzw. anderes Gerüst in dem selben Graphen mit Gewicht existiert. Häufig kürzt man minimal spannender Baum auch mit MST (Abk. des englischen Begriffs Minimum Spanning ab. Statt minimales Gerüst sagt man auch Minimalgerüst .

Minimal spannende Bäume lassen sich mit Kruskal-Algorithmus oder dem Algorithmus von Prim bestimmen wobei die Laufzeit bei einfacher durch <math>O(m \log\ n)</math> und bei der von Fibonacci-Heaps durch <math>O(m + n \log\ n)</math> oben beschränkt ist. (für <math>O(...)</math> siehe O-Notation )

Das Spannbaumproblem tritt in der Praxis bei der kürzesten Verdrahtung von Kommunikationsnetzen auf. für Approximationsalgorithmen für das Problem des Handlungsreisenden lassen sich minimale Spannbäume verwenden.

Näheres siehe unter Wälder und Bäume in der Graphentheorie .

Literatur



Bücher zum Thema Minimal spannender Baum

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Spannbaum.html">Minimal spannender Baum </a>