|
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.
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 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 with n vertices. The formula states that . Another way of stating Cayley's formula is that there are exactly 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 , then , while if G is the n-dimensional hypercube graph , 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. 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. | ||||||||
|
| |||||||||
 |
|
| |