CSC 226: Problem Set 3
Problem Set 3
Network Flows and Probability
Due: 11:55pm Thursday, March 18, 2021
1 Min-Cut and increasing all edge capacities by 1 (10 marks)
A friend makes the following claim: “Let G be an arbitrary flow network and let
(A∗, B∗) be a minimum s-t cut. Now, let’s increase the capacity of each edge by 1.
Then (A∗, B∗) must still be minimum s-t cut.”
Is the friend right? Explain why or why not.
2 Max-Flow with Node Capacities (10 marks)
In a standard Max-Flow problem, we assume that edges have capacities, and there
is no explicit limit on how much flow is allowed to pass through a node. We now
consider a variant of the standard problem where nodes, not edges, have capacities.
Let G = (V,E) be a directed graph, with source s ∈ V , sink t ∈ V , and nonnegative
node capacities cv for each v ∈ V . Given a flow f in this graph, the flow through
a node v is defined as f in(v). We call a flow feasible if it satisfies the usual flow-
conservation constraints and the node-capacity constraints: f in(v) ≤ cv for all nodes.
Show how the Ford-Fulkerson algorithm can be used to find a maximum s-t flow in
such a node-capacitated network.
3 Tragic Comedy and Network Flows (10 marks)
A ship full of k comedians and 2k ordinary (non-comedian) people is capsizing. The
hope is to evacuate all people onboard via rescue boats. Fortunately, each comedian
has one rescue boat (in case they had to escape a tough crowd), and each boat can
carry two additional passengers (for a total of one comedian and two non-comedians).
Therefore, if the non-comedians could be arbitrarily paired up and each pair could
go on one comedian’s boat, everyone could be evacuated.
However, certain ordinary people so strongly dislike the jokes of certain comedians
that they would rather swim than be passengers on those comedians’ boats. More
formally, for each ordinary person pj (for j ∈ {1, 2, . . . , 2k}), there is some subset Sj
of the total set of comedians {c1, . . . , ck} with which they are willing to ride. Under
the constraint that each of the 2k ordinary people needs to be assigned to a boat
operated by a comedian whose jokes they will tolerate, and given that each boat
can hold two ordinary people, the ship passengers wonder whether it is possible to
evacuate everyone aboard.
Show how efficiently answering this question can be reduced to a Max-Flow problem.
4 Probability (not worth any marks, but still important)
A coin comes up heads with probability 1/3 and tails with probability 2/3.
(a) Suppose that the coin is tossed n times. What is the probability that heads occurs
exactly once?
(b) What is the expected number of coin tosses needed to get the first heads?








































学霸联盟