Table of contents

1 Definitionen 2 Beispiele 3 Wichtige Aussagen und Sätze 4 Wichtige Algorithmen 5 Anwendungen

Definitionen

Ein ungerichteter Graph ohne Mehrfachkanten heißt in der Graphentheorie Wald, wenn er keinen nicht-trivialen Kreis enthält. Ist der Graph zudem zusammenhängend, so nennt man ihn Baum.

Ein Knoten in einem Baum heißt Blatt, wenn er Grad 1 besitzt, d.h. nur mit einem anderen Knoten durch eine Kante verbunden ist. Entsprechend heißt ein Knoten in einem Baum innerer Knoten, wenn er kein Blatt ist.

Ein Teilgraph eines ungerichteten Graphen G=(V,E) heißt spannender Baum von G, wenn er Baum ist und alle Knoten von G enthält.

Ein spannender Baum T eines kantengewichteten ungerichteten Graphen G heißt minimal, wenn kein anderer spannender Baum von G existiert, dessen Summe seiner Kantengewichte kleiner ist, als die Summe der Kantengewichte von T. Häufig kürzt man "minimal spannender Baum" auch mit MST ab.

kennt sich jemand mit gerichteten Bäumen aus?

Beispiele

Den Spezialfall eines Baumes, bei dem jeder Knoten vom Grad höchstens drei ist, nennt man Binärbaum.

konkrete Beispiele kommen noch

Wichtige Aussagen und Sätze

1. Ein ungerichteter Graph mit endlich vielen Knoten ist genau dann Baum, wenn er zusammenhängend ist und genau |V|-1 Kanten enthält.
2. Ein Graph ist genau dann zusammenhängend, wenn er einen spannenden Baum enthält.
3. Jeder Baum ist bipartit.
4. Zwischen zwei Knoten eines Baumes gibt es genau einen Pfad.

Zum finden eines minimal spannenden Baumes gibt es den Algorithmus von Kruskal, der Worst-Case-Laufzeit O(|E|ln(|V|)+|V|) besitzt. Etwas schneller ist der Algorithmus von Prim, der Worst-Case-Laufzeit O(|V|ln(|V|)+|E|) besitzt. Dieser benötigt aber mit Fibonacci-Heaps eine recht komplexe Datenstruktur. Man kann zeigen, dass der Algorithmus von Prim damit im wesentlichen bestmöglich ist, da man mit seiner Hilfe auch Zahlen sortieren kann.

Anwendungen

Die Berechnung minimal spannender Bäume findet direkte Anwendungen in der Praxis, wenn man zum Beispiel kostengünstig zusammenhängende Netzwerke herstellen will.