Spanning tree (mathematics)
|
|
Spanning_tree.png
In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree which includes every vertex of that graph. More generally, a spanning forest of an arbitrary undirected graph is a forest which includes every vertex of the graph. 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, involving weighted graphs, it is often useful to find a minimal spanning tree.
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