spanning tree

views updated

spanning tree A subgraph of a connected graph G; this subgraph is a tree and includes all the nodes of G. A minimum-cost spanning tree is a weighted spanning tree, formed from a weighted graph, such that the real numbers assigned to each edge, when summed, total not greater than the corresponding sum for any other weighted spanning tree.