Spanning tree (mathematics)
Encyclopedia : S : SP : SPA : Spanning tree (mathematics)
In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree composed of all the vertices and some (or perhaps all) of the edges of that graph. Informally, a spanning tree of a graph is a selection of edges from the graph that form a tree spanning every vertex. That is, every vertex is connected to the tree, but no cycles (or loops) are formed.
More generally, a spanning forest of an arbitrary, possibly-unconnected, undirected graph is a forest which includes every vertex of the graph and contains a subset of edges of the graph which does not change connected components.
Spanning forests always exist and can always be constructed so as to have exactly one tree for each connected component. In certain fields of graph theory it is often useful to find a minimum spanning tree of a weighted graph.
Cayley's formula is a formula for the number of labelled spanning trees in a complete graph. It states that there are exactly [n^] labelled trees with n vertices. A generalization of Cayley's formula is Kirchhoff's theorem which can be used to calculate the number of spanning trees in any graph.
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.
Examples
- the cycle graph [C_n] with [n] vertices has [n-1] different spanning trees
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.