Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Minimum Spanning Trees

Glossary

spanning tree	T - acyclic and connects all of the vertices of a graph. "Spans" the graph G. (See page 561)



minimum-spanning-tree problem	the problem of determining the spanning tree, T. (See page 561)



safe edge	A greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set of edges A, maintaining the following loop invariant: Prior to each iteration, A is a subset of some minimum spanning tree. At each step, an edge (u, v) is determined which can be added to A without violating this invariant, in the sense that A ∪{(u, v)} is also a subset of a minimum spanning tree. Such an edge is called a safe edge for A, since it can be safely added to A while maintaining the invariant. (See page 562)



cut	A cut (S, V - S) of an undirected graph G = (V, E) is a partition of V. (See page 563)



respects	A cut respects a set A of edges if no edge in A crosses the cut. (See page 563)



light edge	An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut. There can be more than one light edge crossing a cut in the case of ties. More generally, an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property. (See page 563)



second-best minimum spanning tree	Let Τ be the set of all spanning trees of G, and let T' be a minimum spanning tree of G. Then, the second-best minimum spanning tree is a spanning tree T such that w(T) = min_{T'' ∈ Τ - {T'}}{w(T'')}. (See page 575)



spanning tree verification	given a graph G = (V, E) and a tree T ⊆ E, determine whether T is a minimum spanning tree of G. (See page 579)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.