Maximum Flow Assumptions
Download 1 Mb.
|
- Navigate this page:
- Correctness of the algorithm
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
= 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
s S 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. 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:
|