Find \(\varphi(v_i)\) for each vertex, and compute \(\displaystyle \sum_{i=1}^7\varphi(v_i)\text{.}\)
(b)
Classify each vertex as a source, sink and intermediate vertex.
(c)
Add two vertices and as few edges as possible to extend this flow to a flow with a unique source and unique sink
2.
For each of the following capacitated networks, find the max-flow and min-cut on these networks as shown in Section 7.2.
(a)
(b)
(c)
(d)
3.
Consider the max-flow min-cut problem Exercise 7.5.2 (a).
(a)
Write out the non-canonical maximization problem which would compute the max-flow.
(b)
Record this problem in a Tucker tableau, then record the dual variable using \(\ec{\mu_i}\) to denote dual variables associated with vertex equality constraints and \(y_{ij}\) to denote the dual variables for edge inequality constraint.
(c)
Verify that the max-flow and min-cut you found are feasible solutions to these problems (using the convention that \(\mu_k=0\) if \(v_k\in V_1\text{,}\)\(\mu_k=-1\) if \(v_k\in V_2\) and \(y_{ij}=1\) if \(v_i\in V_1, v_j\in V_2\) and \(y_{ij}=0\) otherwise.)
(d)
Argue that any cut corresponds to a feasible solution to this dual problem.
(e)
How can we tell both the flow and cut found in Exercise 7.5.2 (a) are optimal? (Think duality.)
4.
Over a month at a hospital many patients are need of blood transfusions. They had available blood from 47 donors with type A blood, 33 donors with type B blood, 46 donors with type AB and 44 donors with type O. There were 38 patients with type A blood, 39 patients with type B blood, 49 patients with type AB and 43 patients with type O. Type A patients can only receive type A or O, type B patients can receive only type B or O, type O patients can receive only type O, and type AB patients can receive any of the four types.
(a)
Construct a capacitated network which models the distributions of blood type from donors to patients with a unique source and sink, with no edges into the source or out of the sink.
(b)
Find a max-flow for this network.
(c)
Find a min-cut for this network.
(d)
If not all patients were able to receive blood, explain the financial backers and hospital administrators, who may not have taken any math in awhile, why this was the case.
(e)
There’s little a hospital can do about the blood types of incoming patients. If reaching out to potential donors, what blood types should be prioritized?
5.
Let \(N\) be a capacitated network with a unique source and sink, with no edges going into the source or out of the sink. Let \(x_{ij}\) be a flow on this network with value \(f\text{,}\) and \((V_1, V_2)\) be a cut of this network. Then prove that
What is the sum \(\displaystyle \sum_{j\in V_2}\varphi(v_j)\text{?}\) How can rewriting this as a double sum help?
6.
Let \(N\) be a capacitated network with a unique source and sink, with no edges going into the source or out of the sink.
(a)
Given an example for \(N\) such that \(N\) has non-unique max-flows.
(b)
Given an example for \(N\) such that \(N\) has non-unique min-cuts.
(c)
Let \(x_{ij}\) denote any max-flow for \(N\) with value \(f\) and \((V_1, V_2)\) denote any min-cut (not necessarily produced by \(x_{ij}\) and Definition 7.2.12). Let \((V_1', V_2')\) be the cut generated \(x_{ij}\) via Definition 7.2.12.
Prove that \(x_{ij}=c_{ij}\) for any \(v_i\in V_1, v_j=V_2\text{.}\)
Let \(x_{ij}, x'_{ij}\) be two distinct max-flows on \(N\text{,}\) and \((V_1, V_2), (V'_1, V'_2)\) be the cuts produced by Definition 7.2.12 on with these flows respectively. Prove that \((V_1, V_2) = (V'_1, V'_2)\text{.}\)
Hint.
Use previous part.
7.
For each of the following, find the shortest path from \(v_s\) to \(v_d\) using Definition 7.3.7.
(a)
(b)
(c)
(d)
8.
Consider Exercise 7.5.7 (a). Model this problem as a linear optimization problem and solve.
9.
Let \(N\) be a weighted network with positive weights. For the following, prove or find a counterexample:
(a)
Let \(x,y,z\in V\text{.}\) Prove that the value of the shortest path from \(x\) to \(z\) is the sum of the value of the shortest path from \(x\) to \(y\) plus the value of the shortest path from \(y\) to \(z\text{.}\)
(b)
Suppose there was an edge going into \(v_s\text{,}\) then Definition 7.3.7 fails.
10.
For each of the following, find the minimum cost-flows for \(F=8\) and \(F=10\text{.}\) Interpret each ordered pair \((c_{ij}, w_{ij})\) as (capacity,cost).
For each problem in Exercise 6.5.1, draw a weighted capacitated network where the transportation problem may be solved by solving an appropriate min-cost flow problem. State what the value \(F\) of the flow should be. Do not solve the problem.
13.
For each problem in Exercise 6.5.9, draw a weighted capacitated network where the transportation problem may be solved by solving an appropriate min-cost flow problem. State what the value \(F\) of the flow should be. Do not solve the problem.
