Homework 9 (assigned May 28, due June 3)

Reading: CLRS section 24.3; chapter 23

Written assignment: Solve the following exercises and problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both exercises and problems.

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

1. Apply Prim's algorithm to find the minimum spanning tree of the graph given in the Wikipedia entry Prim's algorithm, with vertex A as the source. Use the code Prim given on the course Notes page.
2. Analyze the code Prim, implementing Q as a min-heap. What is the complexity of Prim's algorithm in terms of V and E?
3. Explain how one can identify the connected components of an undirected graph G = (V, E) in O(V+E) time using DFS.
4. Exercise 22.4-3 on CLRS page 552.

Problems (to be handed in):

1. Depth-first search
   Design an efficient algorithm which, given an undirected graph G and a particular edge e in G, determines whether G has a cycle containing e. State the running time of your algorithm and justify your statement. (15 points)

2. Undirected vs. directed connectivity
   
   1. Show that in any connected undirected graph G = (V, E) there is a vertex v in V whose removal leaves G connected. (10 points)
      (Hint: Consider a DFS tree for G.)
   2. A directed graph is called strongly connected if for any pair of two distinct vertices u and v there is a directed path from u to v and a directed path from v to u. Give an example of a strongly connected directed graph G = (V, E) such that, for every v in V, removing v leaves a directed graph that is not strongly connected. (10 points)
   3. In an undirected graph with two connected components it is always possible to make the graph connected by adding only one edge. Give an example of a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected. (10 points)

3. Dijkstra's algorithm
   
   1. Give a simple example of a directed graph with a single negative weight edge (but no negative weight cycle) for which Dijkstra's algorithm outputs incorrect data. Explain briefly what goes wrong. (10 points)
   2. Consider the following algorithm for finding the shortest path from vertex s to vertex t in a directed graph with some negative weight edges (but no negative weight cycles): Add a large constant to each edge weight so that all the edge weights become positive, then run Dijkstra's algorithm starting at vertex s, then return the shortest path found to vertex t.
      Is this a valid method? Either argue that it works correctly or give a counterexample. (15 points)
   3. In cases in which there are several different shortest paths between two vertices, the most convenient of these paths is often the path with the fewest edges. For instance, if vertices represent cities and edge weights represent the costs of flying between cities, there may be several ways to travel from city s to city t which all have the same cost. The most convenient of these routes is the one that involves the fewest stopovers. Accordingly, for a specific source vertex s, define best[u] = minimum number of edges in a shortest path from s to u Give an efficient algorithm for the following problem:
              Input: Graph G = (V, E); positive edge weights w(e); source vertex s.
              Output: The values of best[u] for all vertices u in V.
      (20 points)

4. Minimum spanning trees
   The following statements may or may not be correct. In each case, either prove it (if it is correct), or give a counterexample (if it is not correct). Assume in each case that the graph G = (V, E) is undirected and connected. Do not assume that the edge weights are distinct unless it is specifically stated.
   1. 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.
   2. If a graph G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
   3. Let e be any edge of minimum weight in G. Then e must be part of some MST.
   4. If the lightest edge in a graph is unique, then it must be part of every MST.
   5. The shortest path tree computed by Dijkstra's algorithm is necessarily an MST.
   6. The shortest path between two vertices is necessarily part of some MST.
   (5 points each)