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.
You are given a graph and a max flow on the graph. Show how to
find a minimum cut in O(m) additional time.
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.
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.