Maximum Flow Assumptions



Download 1 Mb.
Page4/6
Date02.05.2018
Size1 Mb.
#47333
1   2   3   4   5   6

end;
Example

1 2



s t

3 4

LIST Pred



s 1 2 3 4 t

1 2

s t

3 4


LIST Pred

s 1 2 3 4 t


1 2

s t

3 4


LIST Pred

s s 1 2 3 4 t

1, 3 0 s 0 s 0 0

2, 3 (Note 2 tries to label only 3) 1

3 3

4 4
The algorithm labels t, augment flow



 = min {2, 3, 5} = 2

1 2

s t

3 4


LIST Pred

s 1 2 3 4 t


1 2

s t

3 4


Can't label anything but s.

Original arcs


1 2

s t

3 4


Correctness of the algorithm
When it stops how do we know we have an optimal solution?
When we stop we can't label the sink.
Let S = set of labeled nodes

= set of unlabeled nodes

sS

t

Since no node in can be labeled by a node in S this implies

rij = 0 for all (i, j)  (S, )

Since



what do we know about xij and xji?

Plug into equation 6.3



 Current flow = capacity of cut [s, ]

By Property 6.1 this implies that x is a maximum flow and [s, ] is a minimum cut.
This establishes the algorithm correctness and the max-flow min-cut theorem.

Download 1 Mb.

Share with your friends:
1   2   3   4   5   6




The database is protected by copyright ©ininet.org 2023
send message

    Main page