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.