Informatik

Was ist ein Wald?

Ein Wald ist ein ungerichteter Graph ohne Zyklen. Jede Zusammenhangskomponente eines Waldes ist ein Baum.

Formelle Definition

Ein Wald W=(V,E)W=(V,E) ist azyklisch. Hat er kk Zusammenhangskomponenten und n=∣V∣n=|V| Knoten, dann gilt ∣E∣=n−k|E|=n-k.

Beispiel

A A B B A--B C C B--C D D E E D--E