maxflow-Research-Operation-Network-Teorem.ppt

A lecture in Operation Research and its application to real life problems.

1. Applications of the
Max-Flow Min-Cut
Theorem

2. S-T Cuts
SF
D
H
C
A
NY
5
6
2
4
5
4
7
S = {SF, D, H}, T={C,A,NY}
[S,T] = {(D,A),(D,C),(H,A)}, Cap [S,T] = 2+4+5 = 11
S = {SF, D, A,C}, T = {H, NY}
[S,T] = {(SF,H),(C,NY)}, Cap[S,T] =6 + 4 = 10
Partition the Nodes into Sets
S and T.
[S,T] = Arcs from Nodes in S
to Nodes in T.

3. Maximum-Flow Minimum-Cut
Theorem
Removing arcs (D,C)
and (A,NY) cuts off
SF from NY.
The set of arcs{(D,C),
(A,NY)} is an s-t cut
with capacity2+7=9.
The value of a
maximum s-t flow =
the capacity of a
minimum s-t cut.
SF
D
H
C
A
NY
5
6
2
4
5
4
7
SF
D
H
C
A
NY
5
6
4
5
4

4. Network Connectivity
An s,t vertex separatorof a graph G=(V,E)
is a set of vertices whose removal
disconnects vertices s and t.
The s,t-connectivityof a graph G is the
minimum size of an s,t vertex separator.
The vertex-connectivityof G is the
min{s,t-connectivity of G: (s,t) in V}.

5. Example
1 8
2
3
4
5
6
7
Some Vertex Separators For s=2, t=7: {3, 4, 6}, {1, 4, 8}
2,7-connectivity = 3
Some Vertex Separators For s=1, t=8: {4, 5, 6}, {2,3}
1,8-connectivity = 2
Vertex-Connectivity = 2

6. Menger’s Theorem
Given and undirected graph G and two
nonadjacent vertices s and t, the maximum
number of vertex-disjoint (aside from
sharing s and t) paths from s to t is equal to
the s,t-connectivity of G.

7. Maximum Flow Formulation
For G=(V,E), construct the network G’=(N,A)
as follows
–For each vertex v in V/{s,t}, add nodes v and v’
–Add arc (v,v’) with capacity 1
–For each edge (u,v) in E, add arcs (u’,v) and
(v’,u) with infinite capacity
–For each edge (s,v) in E, add arc (s,v) with
infinite capacity
–For each edge (v,t) in E, add arc (v’,t) with
infinite capacity

8. Proof
Lemma 1
–Each set of k vertex-disjoint s,t paths in G,
corresponds to exactly one integral flow of
value k in G’.
Lemma 2
–Each s,t cut of finite capacity c corresponds to
an s,t vertex-separator of size c in G
Result follows from Max-Flow Min-Cut
Theorem

9. Finding the Vertex-Connectivity of
G=(N,A)
Let Node 1 be the Source Node s
Let c = |N|
For i = 2 … |N|
–Let t = i
–If s-t Connectivity < c Then
Let c = s-t Connectivity
Return c
Find Vertex-Connectivity of G with |N|-1
Maximum Flow Computations

10. Mining for Gold
Divide a cross-section of earth into a grid of equally-sized
blocks.
Given the cost of excavating a full block and the market
value of a full block of gold, determine an optimal shape
for the mine.
Constraints on the shape of your mine require that a block
of earth cannot be excavated unless the three blocks
above it (directly, and diagonally left and right) have also
been excavated.

12. Solution
To get the gold in block (2,4), we need to
excavate blocks (1,3), (1,4), (1,5) and (2,4).
Revenue = $500, Cost = $400, Profit =
$100. Take block (2,4).
To get the gold in block (3,1), we need to
excavate blocks (3,1), (2,1), (2,2), (1,1),
(1,2) and (1,3). Revenue = $500, Cost =
$500*, Profit = $0. Don’t take block (3,1).
* Assuming (1,3) Already Excavated

13. Maximum Flow Formulation
Each Block is a Node
Add Infinite Capacity Arc from Node (i,j) to
Node (i-1,j-1), (i-1,j),(i-1,j+1)
Add Source Node s and Sink Node t
Wij = Vij -C Where
Vij = Value of Gold in Block (i,j)
C = Cost of Excavating a Block
If Wij < 0, Add an Arc from Node (i,j) to t
with Capacity -Wij
If Wij > 0 Add an Arc from s to Node (i,j)
with Capacity Wij

14. Maximum Flow Network
1,11,21,31,41,5
2,12,22,32,42,5
3,13,23,33,43,5
4,14,24,34,44,5
s
t
400
400
100100
100
100
100

15. Minimum Cut
1,11,21,31,41,5
2,12,22,32,42,5
3,13,23,33,43,5
4,14,24,34,44,5
s
t
400
400
100100
100
100
100
Cut:
S={s,(2,4)(1,3), (1,4), (1,5)}
T: All Other Nodes

16. Meaning of the Minimum Cut
Excavate all Blocks in S
–Only Finite-Capacity Arcs in Minimum Cut
–Blocks in S Can be Excavated Without
Excavating Blocks in T
Arcs in [S,T]
–Arcs from s to Nodes in T
•Capacity = Value of Gold in T
–Arcs from Nodes in S to t
•Capacity = Cost of Excavating S
Cap[S,T] =
Value of Gold in T + Cost of Excavating S

17. Maximizing Profit
Finding a Maximum Flow Minimizes:
Value of Gold in T + Cost of Excavating S
Equivalent to Maximizing:
F = -(Value of Gold in T + Cost of Excavating S )
Equivalent to Maximizing:
Value of All Gold + F =
Value of Gold in S -Cost of Excavating S =
Profit for Excavating S