Exercises on Ch. 3

Minimum Spanning Tree Problem

1. The MST Problem, whose name is the title of this chapter, pertains not to the basic "graphs" of previous chapters, whose edges are dichotomous (either present or absent, represented numerically by 0 and 1 respectively), but to a more general type of "networks" whose edges may have numerical values other than 0 and 1.

   Consider the network in Figure 3.1, page 56.  Construct a different network, which has the same nodes a through g, but all edge values changed from v to 13-v.  That is, edge ab changes from 12 to 1; edge af changes from 3 to 10; edge ag changes from 5 to 8; etc. Draw a diagram for this new network, labeling its edges with the new values.  We wish to find a MST for this new network.  

   • Draw a diagram with nodes only, leaving the edges to be added one by one, as the MST is constructed.
   • List the edges from smallest to largest values, as in Step 1 of Kruskal's algorithm (page 55).
   • Draw in the smallest edge and label it with its value, as in Step 2 of Kruskal's algorithm.
   • Complete step 3 of Kruskal's algorithm, successively examining the next larger edge, adding it if it will not create a cycle, and discarding it if it would.  Draw in and label each edge as it is added to the the MST being constructed.  
   • Repeat step 3 until reaching the link with the highest value. (Alternatively, step 4 tells when one can stop before examining all the links.)
   • Verify that this MST you constructed does indeed span the network.

2.  Repeat the MST construction of the previous exercise, except this time follow Boruvka's algorithm, first adding the smallest edge, then adding independent sets with increasing weights, then repeatedly connecting components using smallest edges.  

3.  The theorems stated by Hage and Harary assert that the two algorithms reach the same end result, which is the MST for the network.  But the intervening steps were different.  Compare the two algorithms, in terms of what the MST-under-construction looked like (a) in exercise 2, at the stage when only Boruvka's independent sets had been added; and (b) in exercise 1, when the same number of edges as in part (a) had been added.