Wälder und Bäume in der Graphentheorie

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. 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.

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 und planar.
• 4. Zwischen zwei Knoten eines Baumes gibt es genau einen Pfad.
• 5. Ein Baum wird zerstörrt durch einfügen einer beliebigen Kante zwischen zwei nicht adjazenten Knoten. Es entsteht ein Kreis.
• 6. Jeder Knoten des Baumes ist für den Zusammenhang notwendig.

Wichtige Algorithmen

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.

Anwendungen

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).

Siehe auch

• Baumstruktur
• Binärbaum
• Dendrogramm
• Baum (Datenstruktur)