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 lies in 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.
In certain fields of graph theory it is often useful to find a minimum spanning tree of a weighted graph. Other optimization problems on spanning trees have also been studied, including the maximum spanning tree, the minimum tree that spans at least k vertices, the minimum spanning tree with at most k edges per vertex (Degree-Constrained Spanning Tree), the spanning tree with the largest number of leaves (closely related to the smallest connected dominating set), the spanning tree with the fewest leaves (closely related to the Hamiltonian path problem), the minimum diameter spanning tree, and the minimum dilation spanning tree.
Read more about Spanning Tree: Fundamental Cycles, Spanning Forests, Counting Spanning Trees, Uniform Spanning Trees, Algorithms
Famous quotes containing the word tree:
“There is something singularly grand and impressive in the sound of a tree falling in a perfectly calm night like this, as if the agencies which overthrow it did not need to be excited, but worked with a subtle, deliberate, and conscious force, like a boa-constrictor, and more effectively then than even in a windy day.”
—Henry David Thoreau (1817–1862)