Homework 9 (assigned November 19, due November 30)

Reading: CLRS chapter 23.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

"Do" Exercises (not to be handed in):

1. Exercise 23.1-5 on page 629.

2. The following statements may or may not be true. In each case, either prove the statement if it is true, or give a counterexample if the statement is false. Always assume the graph G = (V, E) is undirected and connected. Do not assume that the edge weights are distinct unless this is specifically stated.
   • Let e be any edge of minimum weight in G. Then e must be part of some MST.
   • If the lightest edge in a graph is unique, then it must be part of every MST.
   • The shortest path computed by Dijkstra's algorithm is necessarily an MST.
   • Prim's algorithm works correctly when there are negative edges.

3. Exercise 23.1-10 on page 630.

4. Show how to find the maximum spanning tree of a graph, i.e., the spanning tree of largest total weight.

5. Exercise 23.2-8 on page 637.

Assigned Problems (to be handed in):
Important: When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.
Note: You may assume the solutions to the above "Do" exercises without proof in your answers to the assigned problems.

1. Suppose we want to find a minimum spanning tree for the following graph.
   
   • Run Prim's algorithm, starting from vertex A. Whenever there is a choice of vertices, follow alphabetical ordering. Construct tables showing the intermediate values of key[v] and π[v]. What is the resulting MST? What is its weight? (5 points)
   • Run Kruskal's algorithm on the same graph. In what order are the edges added to the MST? For each edge added in this sequence, construct a table giving the cut that justifies the addition of the edge. (5 points)

2. Consider a connected, undirected weighted graph G = (V, E) with nonnegative edge weights w(e) ≥ 0. Suppose that you have computed a minimum spanning tree T of G, and that you have also computed shortest paths to all vertices v in G from a particular vertex s in V. Now suppose that each edge weight is increased by 1: the new weights are c(e) = w(e) + 1.
   • Is T still a minimum spanning tree of G? Either give an example where the minimum spanning tree changes or prove that it cannot change. (5 points)
   • Do the shortest paths change? Either give an example of a shortest path P in G that changes under the new weight assignment or prove that the shortest paths cannot change. (5 points)

3. The following statements may or may not be true. In each case, either prove the statement if it is true, or give a counterexample if the statement is false. Always assume the graph G = (V, E) is undirected and connected. Do not assume that the edge weights are distinct unless this is specifically stated. (5 points each)
   • If a graph G has more than |V| − 1 edges, and there is a unique heaviest edge, then this edge cannot be part of an MST.
   • If a graph G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
   • If e is part of some MST of G, then it must be a lightest edge across some cut of G.
   • If a graph G has a cycle with a unique lightest edge e, then e must be part of every MST.
   • The shortest path between two vertices in G is necessarily contained in some MST of G.

4. In this problem we will develop a new algorithm for computing a minimum spanning tree. It is based on the following property:

   Let G = (V, E) be an undirected, connected, weighted graph with edge weights w(e). Pick any cycle in G, and let e be the maximum-weight edge in that cycle. Then there is a minimum spanning tree of G that does not contain e.

   • Prove this property, i.e., argue carefully and convincingly that the above property is true. (5 points)
   
   The new MST algorithm follows. The input is an undirected, connected graph G = (V, E) in adjacency list representation, with edge weights w(e) for all e in E. The output is an MST of G.
   new_MST(G)
   01 sort the edges according to their weights
   02 for each edge e in E, in decreasing order of w(e)
   03       if e is part of a cycle in G
   04           then G ← G − {e} // i.e., remove e from G
   05 return G
   • Argue carefully and convincingly that this algorithm is correct, i.e., explain how the algorithm works and give reasons why it works; this requires you to explain each step of the algorithm carefully. Give examples if they clarify your argument. Do not give a formal proof of correctness. (5 points)

5. We are given as input a connected, undirected graph G = (V, E) with positive edge weights and a minimum spanning tree T = (V, F) of G with respect to those weights. Both G and T are given in adjacency list representation. Now suppose the weight of a particular edge e = (u, v) not in T is decreased from w(u, v) to a new value c(u, v), i.e., c(u, v) < w(u, v). You want to quickly update the minimum spanning tree T to reflect this change, without recomputing the entire tree from scratch. Give an algorithm for finding the minimum spanning tree in the modified graph.
   • Describe your algorithm in pseudocode. An O(V + E) time algorithm is possible. (10 points)
   • Explain why your algorithm is correct, i.e., explain how it works and argue carefully that its output is a minimum spanning tree of G as modified above. (5 points)

6. One of the basic goals of the minimum spanning tree problem is to design a spanning network for a set of vertices with minimum total cost. In this problem we consider a different objective: designing a spanning network for which the most expensive edge has minimum cost. Specifically, let G = (V, E) be an undirected, connected graph with edge weights w(e) > 0. Let T = (V, F) be a spanning tree of G. We define the bottleneck edge of T to be the edge of T of maximum weight. A spanning tree T of G is a minimum bottleneck spanning tree if there is no spanning tree X of G with a cheaper bottleneck edge, i.e., a bottleneck edge of lesser weight.
   • Is every minimum bottleneck spanning tree of G a minimum spanning tree of G? Prove your answer. If your answer is no, give a counterexample. (5 points)
   • Is every minimum spanning tree of G a minimum bottleneck spanning tree of G? Prove your answer. If your answer is no, give a counterexample. (5 points)