Homework Assignment Six

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
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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

mersin escort adana escort izmir escort gaziantep escort