MS&E 217/317, Combinatorial Optimization, Autumn 2003-04.Instructor: Ashish Goel

Handout 3

HW 2. Given 10/22/2003, Due 10/31/2003, in class, or in my office (by 11am).

No collaboration allowed.

1. Problem 2.9 from the textbook.

2. Problem 2.11 from the textbook.

3. Implement the O(n²)-time variant of Prim’s algorithm, and submit your code by email. Please do not use fancy libraries, user-defined .h files etc. – put your code in a single file. C, C++, Pascal, Basic, Lisp, Fortran, Java are all acceptable. Please do not use any graphics etc – it would be nice if your code compiles and runs on Unix machines.

Assume the following input format:

First line: n

Second line: m

Next m lines: x_i y_i c_i

Here n is the number of vertices, m is the number of edges, x_i, y_i are the endpoints of the i-th edge and c_i is the cost of the i-th edge. Assume that 1 <= i < j <= n. The output should be a set of n-1 edges, each edge on a different line. For each edge, output the two endpoints.

4. Given two spanning trees X and Y, we say that X dominates Y if the j-th cheapest edge in X is no more expensive than the j-th cheapest edge in Y, for 1 <= j <= n-1. Notice that this is a very strong property – much stronger than merely saying that the sum of all edge-costs in X is no more than that the sum of all edge-costs in Y. Prove that every minimum spanning tree dominates every spanning tree of a graph G. (Hint:Think about Kruskal’s algorithm). Observe that problem 2.16 follows as a corollary. Give an example of some other nice corollaries (similar to 2.16) that follow from this strong property.

MS&E 217: Do problems 1,2, and any one of problems 3 and 4.

MS&E 317: If you are going to do the homework for matroids (two problems), do the same homework as above. If not, do all of 1,2,3, and 4.

Note: MS&E 217 students may choose to solve both 3 and 4 for practice/feedback. In that case, I will read all your answers and give comments, but please indicate which of the two you want me to actually grade.