Wald (Graphentheorie)
aus Wikipedia, der freien Enzyklopädie
Als Wald bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Zyklus. Ist dieser zusammenhängend, so spricht man von einem (ungerichteten) Baum. Die Zusammenhangskomponenten eines Waldes stellen in diesem Sinne für sich einen Baum dar, so dass ein Wald aus einem oder mehreren Bäumen besteht.
Jeder ungerichtete Baum ist also auch ein Wald. Betrachtungen über Wälder lassen sich damit auch auf ungerichtete Bäume übertragen. Umgekehrt sind aber auch Betrachtungen über ungerichtete Bäume häufig leicht auf Wälder übertragbar.
Neben ungerichteten Bäumen betrachtet man auch gerichtete Bäume, die häufig auch als gewurzelte Bäume bezeichnet werden und sich weiter in In-Trees und Out-Trees unterscheiden lassen. Die Struktur entspricht im Wesentlichen der von ungerichteten Bäumen, jedoch gibt es einen ausgezeichneten Knoten, den man Wurzel nennt und für den die Eigenschaft gilt, dass alle Kanten von diesem wegzeigen (Out-Tree) oder zu diesem hinzeigen (In-Tree).
Inhaltsverzeichnis |
[Bearbeiten] Algorithmen auf Wäldern
Aufgrund ihrer einfachen Struktur kann die Komplexität von auf Bäumen arbeitenden Algorithmen meist gut abgeschätzt werden. Oft arbeiten die Algorithmen mit einem Baum als Datenstruktur schneller als andere Algorithmen für dasselbe Problem. Beispielsweise ist für das Problem Sortieren das auf Bäumen arbeitende Heapsort schneller als ein eher naives Insertionsort.
[Bearbeiten] Sonderrolle innerhalb der Graphentheorie
Um alle Knoten eines Graphen effizient betrachten zu können, werden aus den bereits erwähnten Gründen gerne Bäume bzw. Wälder aus dem Graphen konstruiert. Dazu eignen sich Verfahren wie Breitensuche oder Tiefensuche auf den Graphen anzuwenden. Das Ergebnis ist ein Spannbaum. Ein minimaler Spannbaum wird unter gesonderter Betrachtung der Kantengewichte konstruiert, wie es durch den Algorithmus von Kruskal oder den Algorithmus von Prim geschieht. Dies dient beispielsweise als Grundlage für Algorithmen zum Problem des Handlungsreisenden.
[Bearbeiten] Wichtige Aussagen und Sätze
- Wälder und Bäume sind bipartit.
- Wälder und Bäume sind planar.
- Wälder und Bäume können topologisch sortiert werden.
- Ein Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.
