1. 3.3.6 2. 3.3.10-b 3. 4.2.13 4. 4.2.6 5. 4.3.2-a,b 6. Two spanning trees on a network N, say T1 and T2, are "neighbors" if T2 can be obtained by T1 by (1) the addition of one arc to T1 to form a cycle; followed by (2), the deletion of one arc in this cycle to form T2. Show that if T1 is not a minimal spanning tree, then it is always possible to find a neighbor of T1 that costs less. (In this way you could construct a lousy MST algorithm for networks by first constructing any spanning tree, and then by moving from cheaper neighbor to cheaper neighbor until no more improvement is possible). To simplify your reasoning, you may assume that the edges in network N have distinct values.

Due: 3/8, in class - but ok to hand in on 3/10, just before exam

-- RobbieMoll - 04 Mar 2004

Topic revision: r3 - 2005-03-06 - RobbieMoll

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback