Wald (Graphentheorie)

Als Wald bezeichnet man in der Graphentheorie einen azyklischen Graphen. Ist dieser zusammenhängend, so spricht man von einem Baum. Jede Zusammenhangskomponente eines Waldes ist ein Baum.

Manchmal ist es sinnvoll, einen Knoten als Wurzel auszuzeichnen. Man spricht dann von einem 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.

Algorithmen auf Wäldern

Aufgrund ihrer einfachen Struktur kann die Komplexität von auf Wäldern 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.
• Ein Graph ist genau dann ein Wald, wenn seine zyklomatische Zahl $0$ ist.

Siehe auch

• Dendrogramm