minimum spanning tree

Given a graph G with weighted edges, a minimum spanning treeMathworldPlanetmath is a spanning treeMathworldPlanetmath with minimum weight, where the weight of a spanning tree is the sum of the weights of its edges. There may be more than one minimum spanning tree for a graph, since it is the weight of the spanning tree that must be minimum.

For example, here is a graph G of weighted edges and a minimum spanning tree T for that graph. The edges of T are drawn as solid lines, while edges in G but not in T are drawn as dotted lines.