- Wald (Graphentheorie)
-
Als Wald oder azyklischen Graphen 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 so erklärter Wald aus Bäumen besteht. Eine Verallgemeinerung auf gerichtete Graphen kann man erklären, indem man diese auf die zugrundeliegenden Ungerichteten zurückführt.
Um eine topologische Charakterisierung, eine Höhe, zu finden, kann es sinnvoll sein, einen Knoten als Wurzel auszuzeichnen. Diese Strukturen heißen Wurzelbaum. Solche Wurzeln kann man einerseits beliebig festlegen. Andererseits gibt es spezielle gerichtete Graphen, wo sich eine Wurzel über die Struktur der Kantenrichtungen von selbst erklärt, etwa als einziger Knoten ohne eingehende/ausgehende Kante. Solche Bäume heißen In-, beziehungsweise Out-Trees. Die In- und Out-Wälder sind dann Graphen mit mehreren solchen Komponenten.
Inhaltsverzeichnis
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.
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 oder 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.
Gegenbeispiel: gerichtet azyklische Graphen müssen keine Wälder sein
Wichtige Aussagen und Sätze
- Alle Wälder sind bipartit. Eine Bipartition bekommt man, indem man die Knoten bezüglich ihrer Distanz modulo 2 zu einem beliebig, fest gewählten Knoten zusammenfasst.
- Alle Wälder sind planar.
- Genau alle gerichtet azyklischen Graphen können topologisch sortiert werden, gerichtete Wälder also insbesondere.
Siehe auch
Wikimedia Foundation.
