Guest User

Untitled

a guest
Jul 16th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.69 KB | None | 0 0
  1. Consider the residual graph G_f
  2. 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.
  3. 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
  4. Accordingly this means there is a forward path from s to u and v to t.
  5. However since this is under max flow there cannot be a s-t path thus there is no forward edge between u and v.
  6. 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