Instructors: Martin Savelsbergh & Masoud Talebian Operations Research I: Spanning Tree Problems
Definition 2 1 4 3 A spanning tree is a connected subset of a network including all nodes, but containing no cycles. 5 2 1 4 3 5 2 1 4 3 5 2 1 4 3 5
Minimum Cost Spanning Tree ?Suppose that each arc (i,j) in a network has a length associated with it and that arc (i,j) represents a way of connecting node i to node j. ?In many applications (electricity, computers, ICs, etc), we want to determine the set of arcs in a network that connect all nodes such that the sum of the length of the arcs is minimized. Clearly, such a group of arcs contain no loop. ?For a network with n nodes, a spanning tree is a group of n-1 arcs that connects all nodes of the network and contains no loops. ?A spanning tree of minimum length in a network is a minimum spanning tree (MST).
Is LP formulation possible? ?Nodes are not pre-specified as origins or destinations, so we do not formulate as LP model
?Begin at any node i, and join node i to the node in the network (call it node j) that is closest to node i. ?The two nodes i and j now form a connected set of nodes C={i,j}, and arc (i,j) will be in the minimum spanning tree. The remaining nodes in the network (call them C’) are referred to as the unconnected set of nodes. ?Now choose a member of C’ (call it n) that is closest to some node in C. Let m represent the node in C that is closest to n. Then the arc(m,n) will be in the minimum spanning tree. Now update C and C’. Since n is now connected to {i,j}, C now equals {i,j,n} and we must eliminate node n from C’. ?Repeat this process until a minimum spanning tree is found. Ties for closest node and arc to be included in the minimum spanning tree may be broken arbitrarily. MCST Algorithm
Example: ?University of Newcastle campus has five computers. The distances between each pair of computers are given. ?What is the minimum length of cable required to interconnect the computers? ?Note that if…