ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 3 - WRITTEN

1. Suppose G is a connected graph with distinct positive integer edge weights. Prove that G has exactly
one minimum spanning tree T. You may invoke the cut property and/or the cycle property if needed.
2. Modify the statement of the cut property so that it is true, even for the case of edge weights that are
not necessarily distinct. Prove that your modified statement is true when edge weights may be
repeated.
3. Consider the following graph � = (�, �), where each edge � = (�, �) has a weight �(�, �), � =
{�, �, �, �, �} and � = {(�, �), (�, �), (�, �), (�, �), (�, �), (�, �), (�, �)}. The weights on the edges
are:
We define the profile of a graph � to be the list of its edge weights in non-decreasing order. For
example, in the graph � above, the profile is 1,1,2,2,3,3,3. The profile of an MST � is the list of its
edge weights in non-decreasing order.
Find every MST � for the graph � above: for each �, list the edges in alphabetical order, give the
weight of � and its profile �. We know that the weights of all the MSTs, by definition, must be the
same. Based on the results can you make a conjecture about profiles of MST’s?
4. In the Algorithms, 4th Edition textbook by Sedgewick, in Chapter 1.5 he develops an implementation
of the union-find data structure using an integer array of size � for � vertices called the site-indexed
id[] array. Show the contents of the id[] array along with the corresponding forest of trees
representation (see example on page 225) for each input pair 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2 when you
use the weighted quick-union algorithm (page 228). This algorithm corresponds to the union-by-size
algorithm discussed in lecture. (This is actually exercise 1.5.3 in the text.)
5. For that matter, why don’t you do exercise 1.5.9 from the textbook while you’re at it. Draw the tree
corresponding to the id[] array given below:
i 0 1 2 3 4 5 6 7 8 9
id[i] 1 1 3 1 5 6 1 3 4 5
Can this be the result of running weighted quick-union? Explain why this is impossible or give a
sequence of operations that results in this array