Wälder und Bäume in der Graphentheorie

Inhaltsverzeichnis

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

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 Knoten durch eine Kante verbunden ist. Entsprechend 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 von T . Häufig kürzt man "minimal spannender Baum" mit MST ab.

Ein gerichteter Graph mit endlich vielen heißt Baum g.d.w. | V |-1 Knoten einen Eingansgrad von 1 besitzen 1 Knoten einen Eingangsgrad von 0 besitzt. Knoten ist die Wurzel des Baumes.

Wichtige Aussagen und Sätze

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

Wichtige Algorithmen

Mittels Tiefensuche kann leicht ein linearer Algorithmus implementiert der zu einem zusammenhängenden Graphen G =( V E ) einen spannenden Baum berechnet.

Zum finden eines minimal spannenden Baumes 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 Prim damit im wesentlichen bestmöglich ist da mit seiner Hilfe auch Zahlen sortieren kann.

Anwendungen

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

In der Graphentheorie selbst sind MST-Algorithmen Grundlage komplexerer Algorithmen für schwierigere Probleme. Die minimal spannender Bäume ist zum Beispiel Bestandteil Approximations-Algorithmen für das Steinerbaum-Problem oder für das Problem des Handlungsreisenden (oft auch Traveling-Salesman-Problem genannt und TSP abgekürzt).

Siehe auch

• Baumstruktur
• Binärbaum
• Dendogramm

Bücher zum Thema Wälder und Bäume in der Graphentheorie

Dieser Artikel von Wikipedia unterliegt der GNU FDL.