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:
“A tree is made to live in peace in the color of day and in friendship with the sun, the wind and the rain. Its roots plunge in the fat fermentation of the soil, sucking in its elemental humors, its fortifying juices. Trees always seem lost in a great tranquil dream. The dark rising sap makes them groan in the warm afternoons. A tree is a living being that knows the course of the clouds and presses the storms because it is full of birds’ nests.”
—Jacques Roumain (1907–1945)