Spanning tree (mathematics)
From Free net encyclopedia
Image:Spanning tree.png In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree composed of all vertices and some 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, no vertex is not connected to the tree.
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 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 <math>n^{(n-2)}</math> 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 between all the spanning trees with equal probability is called a uniform spanning tree, or UST for short. This model has been extensively researched in probability and mathematical physics.
Examples
- the cycle graph <math>C_n</math> with <math>n</math> vertices has <math>n-1</math> different spanning treescs:Kostra grafu