MIME-Version: 1.0 Server: CERN/3.0 Date: Sunday, 24-Nov-96 22:41:36 GMT Content-Type: text/html Content-Length: 1645 Last-Modified: Friday, 27-Sep-96 00:34:17 GMT CS 681: Homework 3

CS681 Homework 3

September 20, 1996

  1. Consider the following problem: A town has r residents R1,...,Rr; q clubs C1,...,Cq; and p political parties P1,...,Pp. Each resident is a member of at least one club and belong to exactly one political party. Each club must nominate one of its members to represent it on the town's governing council so that the number of council members belonging to the political party Pk is at most uk (for given u1,...,up). It is not ok for two or more clubs to nominate the same person. The problem is to determine whether it is possible to find a council that satisfies this "balancing" property.

    Given r, R1,...Rr,q,C1,...Cq,p,P1,...,Pp,u1,...up, show how to solve this problem by solving a single max flow problem.

  2. You are given a graph and a max flow on the graph. Show how to find a minimum cut in O(m) additional time.

  3. Show how to transform a maximum flow problem having several source nodes and several sink nodes to one with only one source node and one sink node.

  4. Construct an easy to describe family of flow graphs (the ith flow graph is a graph on i nodes) with the number of cuts of minimum capacity growing exponentially with i.

Due September 27 in class.