Maximum Flow Assumptions

Theorem 6.3 (Max-Flow Min-Cut Theorem)

Download 1 Mb.

Page	5/6
Date	02.05.2018
Size	1 Mb.
	#47333

1 2 3 4 5 6

Theorem 6.3 (Max-Flow Min-Cut 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 s-t 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 Ford-Fulkerson method
1. Empirically Ford-Fulkerson 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_ijvalues, 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 Max-Flow Min-Cut Theorem). If the capacity of an s-t 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 s-t 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

Directory: ~banwork -> 3087
3087 -> Improved max flow path augmenting
3087 -> Assignments and Matchings Match workers to jobs, etc

Download 1 Mb.

Share with your friends:

1 2 3 4 5 6