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. 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.
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.
[edit] References
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.1: ND2, pg.206.
