Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Consider the residual graph G_f
- We first note the fact that once a graph has obtained its max flow there cannot be any s-t paths within in the residual graph as that means we still have yet to fully saturate all paths.
- Suppose A_o and B_1 non empty (if empty this is trivially true) and let u in A_o and v in B_1
- Accordingly this means there is a forward path from s to u and v to t.
- However since this is under max flow there cannot be a s-t path thus there is no forward edge between u and v.
- Accordingly if we increase the capacity of edge (u,v) by one we create a forward edge between (u,v) with capacity 1, thus allowing one more flow thus increasing max flow by 1 and achieving Gā as desired.
Add Comment
Please, Sign In to add comment