Spannbaum

Spannbaum is the German term for the graph-theoretic concept of a spanning tree. For a connected undirected graph G = (V, E), a Spannbaum T is a subgraph that is a tree and includes all vertices of G. Equivalently, T has V(T) = V and E(T) ⊆ E, and T is connected and acyclic. Consequently, a Spannbaum contains exactly |V| − 1 edges. If G is disconnected, a spanning forest is a collection of spanning trees, one for each connected component.

Spanning trees provide a minimal, cycle-free backbone of a network that preserves reachability among all vertices. In weighted graphs, a spanning tree of minimum total edge weight is called a minimum spanning tree (MST). A MST may not be unique if edge weights are not all distinct; common methods to construct one MST include Prim's algorithm and Kruskal's algorithm.

Key properties include that any spanning tree of a connected graph with n vertices has exactly n−1 edges, and the number of different spanning trees can be large; for the complete graph K_n, Cayley’s formula states there are n^(n−2) spanning trees.

Variants and related concepts include spanning arborescences in directed graphs, which are rooted trees that span all reachable vertices, and spanning forests for disconnected graphs. Spannbäume are widely used in network design, clustering, and hierarchical decomposition due to their simplicity and their guarantee to connect all vertices without forming cycles.