Wälder und Bäume in der Graphentheorie
Table of contents |
2 Wichtige Aussagen und Sätze 3 Wichtige Algorithmen 4 Anwendungen 5 Siehe auch |
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. Eine Menge von disjunkten Bäumen bildet also einen Wald.
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. Häufig wird dabei ein Blatt als Wurzel ausgezeichnet.
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.
Ein gerichteter Graph heißt gerichteter Baum, wenn der zugrundeliegende ungerichtete Graph ein Baum ist. Existiert weiterhin genau ein Knoten ohne Eingangskanten (also Eingangsgrad ist Null ), so heißt dieser Knoten Wurzel und der Graph Wurzelbaum. Wie bei Baum (Datenstruktur) heißt ein Knoten A mit einer Kante nach B Elternknoten oder auch Vater des Sohnes B. Existiert ein gerichteter Weg von einem Knoten C zu einem anderen Knoten D, so heißt D Nachfolger oder Nachkomme von C und C Vorgänger oder Vorfahre von D. Der Teilbaum TB eines Knoten E des gerichteten Baum T besteht aus allen Knoten, die Nachfolger von E sind und allen Kanten von T, die diese Knoten verbinden. Ein Teilbaum ist also eine Teilmenge eines gerichteten Baums, die selber ein gerichteter Baum ist. Ein Wurzelbaum dessen größter vorkommender Ausgangsgrad q ist, heißt q-närer (Wurzel-)Baum - i. B. binärer Baum.
Mittels Tiefensuche kann leicht ein linearer Algorithmus implementiert werden, der zu einem zusammenhängenden Graphen G=(V,E) einen spannenden Baum berechnet.
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.
Wälder und Bäume sind azyklische Graphen und können daher topologisch sortiert werden,
siehe Topologisches Sortieren.
Die Berechnung minimal spannender Bäume findet direkte Anwendungen in der Praxis, wenn man zum Beispiel kostengünstig zusammenhängende Netzwerke herstellen will.
In der Graphentheorie selbst sind MST-Algorithmen häufig Grundlage komplexerer Algorithmen für schwierigere Probleme. Die Berechnung minimal spannender Bäume ist zum Beispiel Bestandteil von Approximations-Algorithmen für das Steinerbaum-Problem oder für das Problem des Handlungsreisenden (oft auch Traveling-Salesman-Problem genannt und TSP abgekürzt).Definitionen
Wichtige Aussagen und Sätze
Wichtige Algorithmen
Anwendungen