Due Friday, Mar 27th in class.
Submissions: Please submit your printed or hand written solutions in class. If you have a compelling reason for not being able to attend that particular class, please email your submissions to the instructor or the TA.
Policy: Write your own solutions independently; include the names of anyone you discussed the problems with.
1. Let be an undirected graph with capacities on each edge . Let be two of its vertices. Let be the set of paths in and be the subsets of edges that are cuts. Show that
2. Show that in any graph with a valid flow on its edges,
(a) The flow from to can be decomposed into paths and simple cycles (no repeated vertices). In other words, each path from to carries a flow of value on its edges and each cycle carries a flow of value on its edges. The total flow on an edge is equal to the sum of the flow values of all paths and cycles containing the edge.
(b) Given capacities on the edges, there is a maximum flow with no cycles.
3. Let be a closed convex set in . Show that for any point not in , there is a vector and a real value s.t. and for every .
4. Write a linear program for the maximum flow problem in a directed graph, using one flow variable for every path from the source s to the sink t (so the number of variables could be exponential in the size of the graph). Then write the dual of the program and interpret the variables, constraints and objective value of the dual.
5. (Bonus) Write an LP for the maxflow problem using flow variables, one for each edge. Write the dual and argue that it represents a minimum s-t cut.