Spanning

Spanning, in mathematics, denotes the idea that a subset can generate or cover a larger object through allowed operations. In linear algebra, the span of a set S of vectors in a vector space V is the set of all finite linear combinations of vectors in S. The span is a subspace of V. If Span(S) equals V, S is a spanning set for V; if S is additionally minimal, it is a basis, and its size is the dimension of V. Example: in R^3, the standard basis e1, e2, e3 spans all of R^3; the set {(1,0,0),(0,1,0)} spans the xy-plane.

In graph theory, a spanning subgraph of a graph G=(V,E) is a subgraph with the same vertex set V and a subset of edges. The term spanning tree refers to a spanning subgraph that is a tree; for a connected graph with n vertices, any spanning tree has n−1 edges. A graph may contain many spanning trees; those with minimal total edge weight constitute a minimum spanning tree, a central object in network design and algorithms.

Spanning concepts also appear in other mathematical areas, including topology and combinatorics, where they describe ways to cover or generate larger structures from smaller generating sets. In each context, spanning captures the idea of extending a system to reach or connect all required elements, either by forming linear combinations in vector spaces or by selecting edges to connect all vertices in a graph.