Spannbaum

Zusammenfassung

Ein Spannbaum ist ein Teilgraph der ein Baum ist und alle Knoten enthält.

Def. Spannbaum

Es sei $G = (V, E)$ ein Ungerichteter Graph. Ein Spannbaum von $G$ ist ein Teilgraph von $G$, der ein Baum ist und jeden Knoten $v \in V$ enthält.