Informatik

Was ist ein Spannbaum?

Ein Spannbaum eines zusammenhängenden Graphen $G$ ist ein Teilgraph, der alle Knoten von $G$ enthält und ein Baum ist, das heißt, er ist zusammenhängend und zyklenfrei.

Formelle Definition

Ein Spannbaum $T$ eines Graphen $G = (V, E)$ hat die Eigenschaften:

• $V(T) = V(G)$
• Der Baum hat genau $|V| - 1$ Kanten.

Beispiel

Gegeben sei der Graph $G$:

Ein möglicher Spannbaum $T$ aus $G$ könnte sein: