Theorem 6.3 (MaxFlow MinCut Theorem). The maximum value of the flow from a source node s to a sink node t in a capacitated network equals the minimum capacity among all st cuts.
Similarly, we can show
Theorem 6.4 (Augmenting Path Theorem). A flow x* is a maximum flow if and only if the residual network G(x*) contains no augmenting path.
We can also show
Theorem 6.5 (Integrality Theorem). If all arc capacities are integer, the maximum flow problem has an integer maximum flow.
Complexity
0(m) per augmentation
max nU (increase flow by 1 each time)
0(nmU)
If there are infinite capacity arcs just set u_{ij} very large but finite.
Drawbacks of the FordFulkerson method
1. Empirically FordFulkerson does well but can construct pathological
problems (see book).
2. Irrational capacities cause complications
3. "Forgetfulness"  start labeling over each time  we will discuss
improvements.
Flows with Lower Bounds
l_{ij } 0
max v
s.t.
Two key steps

Show that a feasible flow exists
(l_{ij}, u_{ij})
(6, 9) (4, 5)
Infeasible Example 1 2 3
2. Find the maximum flow
Consider finding maximum flow first.
Assume we have a feasible flow.
Now with one modification we can use prior algorithms.
Let r_{ij}=(u_{ij } x_{ij}) + (x_{ji}  l_{ji})
Since the flow is feasible => l_{ij } x_{ij} u_{ij} = > r_{ij} 0
Our algorithms work with r_{ij} values (not arc flows, capacities, or lower bounds) so we can still use them.
One way to construct maximum flows, x_{ij }values, from r_{ij} values
For (i, j) let
u_{ij} = u_{ij}  l_{ij} r_{ij} = r_{ij}
x_{ij} = x_{ij}  l_{ij}
recall
r_{ij} = (u_{ij}  x_{ij}) + (x_{ji}  l_{ji})
equivalently
r_{ij} = (u_{ij}  x_{ij} + x_{ji})
similarly
r_{ji} = (u_{ji } x_{ji} + x_{ij})
compute x as before
x_{ij} = max (u_{ij}  r_{ij}, 0)
x_{ji} = max (u_{ji}  r_{ji}, 0)
In original variables
x_{ij} = l_{ij} + max (u_{ij}  r_{ij}  l_{ij}, 0)
x_{ji} = l_{ji} + max (u_{ji}  r_{ji}  l_{ji}, 0)
Using the modified r_{ij} values we will find an optimal solution and can prove theorem 6.10
Theorem 6.10 (Generalized MaxFlow MinCut Theorem). If the capacity of an st cut [s, ] in a network with both lower and upper bounds on arc flows is defined by (6.7), the maximum value of flow from node s to node t equals the minimum capacity among all st cuts.
(6.7)
How find a feasible flow?
First transform to a circulation problem.
Add
(t, s) with u_{ts} =
Find a flow satisfying
(6.11)
let x_{ij} = x_{ij}  l_{ij}
Now
(6.2)
Note
Like feasible flow in application 6.1.
The maximum flow problem has a feasible solution iff the circulation has a feasible flow.
Can show theorem 6.11
Share with your friends: 