Wälder und Bäume in der Graphentheorie
Wälder und Bäume sind in der Graphentheorie spezielle Graphen, wobei ein Wald aus einem oder mehr Bäumen besteht. Somit sind Betrachtungen über Bäume auch auf Wälder übertragbar.Aufgrund ihrer einfachen Struktur, kann die Komplexität der darauf arbeitenden Algorithmen 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 Graphs 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 bspw. als Grundlage für Algorithmen zum Problem des Handlungsreisenden.
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.