Due: Tuesday October 31 at the beginning of class (10am).

Reading: Sections 5.1, 5.2, 5.5(upto Thm 5.5.2), and Chapter 6

Problems:

1. Suppose (G,w) is a network and R is a subset of vertices such that the distance between any two vertices in R is at most r. Let z be a vertex whose distance from any vertex in R is greater than r. Prove or disprove the following statement:

               A minimal Steiner Tree for (G,R,w) cannot contain z.

2. Suppose M=(E,S) is a matroid and A is a maximal independent subset of E with maximum weight for some non-negative weight function w(). Prove that there is some sorting of E into non-increasing order of w() so that the solution constructed by GREEDY is A.

3. Let G be a graph whose edges have been colored red and blue. Consider the independent system M = (E,S) where S contains all subsets of edges A such that each component of (V,A) is either acyclic or has just one cycle which has an odd number of blue edges. Show that M is a matroid.

4. Perform the Edmonds-Karp algorithm on the network below to find a maximum flow. Label the nodes in breadth-first order to find an augmenting path. Use one copy of the network for each labeling iteration and ``highlight'' the augmenting path found. In the last iteration, draw the minimum cut that corresponds to the maximum flow. If you don't want to copy the network yourself click here for a page with 10 copies of the network.

Solutions (postscript)