Spanning Trees and Minimum Spanning TreesWhat is a (Minimum) Spanning Tree in a graph?A spanning tree in a graph G=(V,E) is an acyclic, connected subgraph of G, that contains all vertices of G.A minimum spanning tree in a graph G=(V,E) with weights on the edges is a spanning tree such that the sum of the edge weights of the edges in the tree is minimum. The LEDA functions

See also:Manual Entries: Minimum Spanning Trees 