Spanning tree (mathematics)
From Wikipedia, the free encyclopedia
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex. That is, every vertex is connected to the tree, but no cycles (or loops) are formed. On the other hand, every bridge of G must belong to T.
A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices.
More generally, a spanning forest of an arbitrary (possibly unconnected), undirected graph G is a maximal forest that is a subgraph of G. Equivalently, a spanning forest is the union of a spanning tree for every connected component of G.
In certain fields of graph theory it is often useful to find a minimum spanning tree of a weighted graph.
[edit] Counting spanning trees
The number t(G) of spanning trees of a connected graph is an important invariant. In some cases, it is easy to calculate t(G) directly. It is also widely used in data structures in different computer languages. For example, if G is itself a tree, then t(G)=1, while if G is the cycle graph Cn with n vertices, then t(G)=n. For any graph G, the number t(G) can be calculated using Kirchhoff's matrix-tree theorem (follow the link for an explicit example using the theorem).
Cayley's formula is a formula for the number of spanning trees in the complete graph Kn with n vertices. The formula states that t(Kn) = nn − 2. Another way of stating Cayley's formula is that there are exactly nn − 2 labelled trees with n vertices. Cayley's formula can be proved using Kirchhoff's matrix-tree theorem or via the Prüfer code.
If G is the complete bipartite graph Kp,q, then t(G) = pq − 1qp − 1, while if G is the n-dimensional hypercube graph Qn, then 
. These formulas are also consequences of the matrix-tree theorem.
If G is a multigraph and e is an edge of G, then the number t(G) of spanning trees of G satisfies the deletion-contraction recurrence t(G)=t(G-e)+t(G/e), where G-e is the multigraph obtained by deleting e and G/e is the contraction of G by e, where multiple edges arising from this contraction are not deleted.
[edit] Uniform spanning trees
A spanning tree chosen randomly from among all the spanning trees with equal probability is called a uniform spanning tree (UST). This model has been extensively researched in probability and mathematical physics.
