Solutions -- Analysis of Algorithms, part 1, CS 288,
May 8, 2006

 

  1. The successive values of d and π are given below. The set S initially contains 0; successive iterations add the vertices 1, 3, 4, 5, and 2 in that order. In π the value 0 stands for nil
    d   π
    1 2 3 4 5   1 2 3 4 5
    ∞ ∞ ∞ ∞ ∞  0 0 0 0 0
    2 9 3 7 9  0 0 0 0 0
    2 8 3 6 8  0 1 0 1 1
    2 8 3 6 7  0 1 0 1 3
    2 8 3 6 7  0 1 0 1 3
    2 8 3 6 7  0 1 0 1 3

    The shortest paths are the paths from vertex 0 in the spanning tree below:

     

    1. If e = {u,v}, then there is already a path P between u and v in O. So adding e to P creates a cycle.

    2. K contains no cycles, so it can't contain every edge of the given cycle.

    3. It's clear that the resulting graph has the same number of edges as O. We need to show either that G is connected or that G is acyclic (it's a theorem that either one of these properties entails the other, given the proper edge count). To show that G is connected, let x and y be two vertices of G. Then there's a path in G between x and y, since G contains all the edges of O. If f = {w,z}, then we may assume that f is not part of this path -- we know there's another path between w and z since f is part of a cycle in G. So this path still exists when f is removed. Since x and y are arbitrary, the resulting graph is connected.

      The proof of the that G has no cycle would observe that G has 1 connected component, that when all G's edges are removed, it has as many components as vertices, and that adding each edge back to G would reduce the number of components by exactly one -- so it must be that adding each edge reduces the number of components by 1 and thus does not create a cycle.

    4. It's enough to show that e is no more expensive that f. But if f is cheaper than e, then Kruskal's algorithm would have considered f before e, and added it to K (adding f could not have created a cycle, since the spanning tree under construction would contain only edges of O).

    5. The new spanning tree contains e (we added it), and all of the edges of K that are cheaper than e (since they were in O, and were not removed). Since O" has a later first difference than O, there can be no O with the given property. It was already noted that the nonexistence of such an O means that K is optimal.

     

  3. Coverting to slack form, we see that the task is to maximize x1 + x2 + x3 subject to 
       z1 = 4 - x2 - x3 
   z2 = 0 - x1 - x2 + x3  
   z3 = 0 + x1 + x2 - x3
    Since x1 has a positive coefficient in the objective function, we solve the second constraint for it, so that we are now maximizing 2x3 - z2 subject to 
       x1 = 0 - x2 + x3 - z2  
   z1 = 4 - x2 - x3
   z3 = - z2
    Now x3 has a positive coefficient in the objective function. We solve the z1 constraint for it, so that we are now maximizing 8 - 2x2 - 2z1 - z2 subject to 
       x1 = 4 - 2x2 - z1 - z2
   x3 = 4 - x2 - z1
   z3 = - z2
    All coefficients of variables in the objective function are now negative, so its maximum value is 8, and this value is attained by giving x1 and x3 each the value 4, and x2 the value 0.