image/svg+xml
Math3012AppliedCombinatorics
Goal:How hard is findingmaximal flows?
(flow) network
sourcesinkcapacity
5
5
10
10
6
2
1
7
b
c
f
e
t
s
1
1
3
4
4
1
1
5
flow
Max Flow Min Cut Theorem
The maximum value of any flow isequal to the minimum capacity ofany cut.
Ford Fulkerson
secbt augmenting path slack 3
({s,e,c},{b,f,t}) cut capacity 5
What complexity is the Network Flow Problem?
106
106
106
106
1
0
1
s
t
Edmund's Karp Algorithm
'Ford-Fulkerson labeling'
Construct augmenting paths bybreadth first search
The most flow without going over capacity