Maximum Flow Assumptions


Theorem 6.3 (Max-Flow Min-Cut Theorem)



Download 1 Mb.
Page5/6
Date02.05.2018
Size1 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 uij 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
lij  0
max v

s.t.



Two key steps

  1. Show that a feasible flow exists

(lij, uij)


(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 rij=(uij - xij) + (xji - lji)

Since the flow is feasible => lij  xij  uij = > rij  0

Our algorithms work with rij values (not arc flows, capacities, or lower bounds) so we can still use them.
One way to construct maximum flows, xij values, from rij values
For (i, j) let

uij = uij - lij rij = rij

xij = xij - lij
recall

rij = (uij - xij) + (xji - lji)


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

xij = lij + max (uij - rij - lij, 0)

xji = lji + max (uji - rji - lji, 0)

Using the modified rij 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 uts = 


Find a flow satisfying


(6.11)

let xij = xij - lij


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


Download 1 Mb.

Share with your friends:
1   2   3   4   5   6




The database is protected by copyright ©ua.originaldll.com 2024
send message

    Main page