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:
“Happy are those who find wisdom, and those who get understanding, for her income is better than silver, and her revenue better than gold. She is more precious than jewels, and nothing you desire can compare with her. Long life is in her right hand; in her left hand are riches and honor. Her ways are ways of pleasantness, and all her paths are peace. She is a tree of life to those who lay hold of her; those who hold her fast are called happy.”
—Bible: Hebrew, Proverbs 3:13-18.