Optimización

Chapter 5

Minimum Spanning Trees
This chapter is based on well-known results. Our discussion follows Ahuja, Magnanti & Orlin 1, Chapter 13] and the survey by Magnanti and Wolsey 8]. The focus of this chapter is on the linear programming formulation of the minimum spanning tree problem due to Edmonds. Also, we describe the well-known algorithms of Kruskal and Prim for nding minimumspanningtrees. For further details and data structures for e ciently implementing these algorithms, we refer the reader to Cormen et al 4].

5.1 Applications
We start with some applications of the minimum spanning tree problem. (a) Minimum-cost road interconnection network: There are n towns in a region. For certain pairs i and j it is feasible to build a direct road between i and j , and there is a costcij incurred if the road ij is built. The problem is to construct enough roads so that every pair of towns can communicate (perhaps indirectly), and the total construction cost must be minimized. (b) Finding routes with maximum bottleneck capacity: There are n computers connected by a network such that for certain pairs i and j there is a direct link with a capacity of cij bits/second. For eachpair of computers, the problem is to nd a path between them (i.e., a sequence of direct links) such that the bottleneck capacity (i.e., the smallest link capacity in the path) is as large as possible. (See Problem 3 for more details.) (c) Reducing data storage: There is a 2-dimensional array such that the rows have similar entries and di er only at a few places. Let cij denote the number of di erententries in rows i and j . The problem is to store the array using a small amount of storage space. One solution is to store a reference row i completely, and for the remaining rows j to store only the positions and entries where rows i and j di er. 64

5.2. TREES AND CUTS

65

(d) Cluster analysis: Given a set of n data points, the problem is to partition it into \clusters" such that datapoints within a cluster are \closely related" to each other. Kruskal's minimum spanning tree algorithm (see Section 5.4) maintains \clusters" and at each iteration \merges" the \closest" two clusters. The algorithm starts with n clusters, and ends with one. Each stage of the algorithm gives a partition of the data points into clusters. Consequently, several solutions to the clustering analysisproblem can be found by running Kruskal's algorithm on the given data points.

5.2 Trees and cuts
This section has some fundamental results on trees and cuts that are used in this chapter and the later chapters. We recall a few de nitions from Chapter 1. A tree is a connected graph that has no cycles. Given a node set Q V , (Q) denotes the set of all edges with one end in Q and the other end in VnQ. A cut consists of all edges that have one end in Q and the other end in V nQ, where Q is a node set. this cut is denoted (Q V nQ). Clearly, if 6= Q 6= V , then (Q) = (Q V nQ).

Proposition 5.1 A graph G = (V E ) is connected if and only if for every node set Q
6= Q 6= V , (Q) 6= .

V,

because for any node v 2 Q and any node w 2 V nQ (both v and w exist) there is no path from v to w inG. For the other direction, start with any node v let Q = fvg and let F be an edge set that is initially empty. As long as Q 6= V , there is an edge qz in (Q) with q 2 Q and z 62 Q. Repeatedly, add the edge qz to F and add z to Q. By induction on the number of steps, observe that the subgraph (Q F ) contains a path from the start node v to each node q 2 Q. Hence, when Q = V , then (Q F ) is aconnected spanning subgraph of G, implying that G is connected. (In fact, the nal F is (the edge set of) a spanning tree of G.)

Proof: Suppose that there is a node set Q, 6= Q 6= V , with (Q) = . Then G is not connected

Theorem 5.2 Let T = (V F ) be a graph. The following statements are equivalent:
(a) T is a tree, or equivalently, T is connected and has no cycles. (b) There is exactly one...