Pancake's blog

how to prove something related to Ford-Fulkerson method
By Pancake, 12 years ago, In English

Hello All.Recently I have been trying to study the Ford-Fulkerson method to compute a maximum network flow in depth , and I can't find out how to prove the following property: After finding an augmenting path in the residual network , the flow-in = flow-out rule will still hold for every node in the network (not including the source and the sink nodes) . Any help on this is appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Very good book: "Introduction to Algorithms" Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Of course "the flow-in = flow-out rule will still hold for every node" "After finding an augmenting path". Just finding an augmenting path changes nothing. Each edge still has the same flow. Then for each node from augmenting path we increment flow by value X to one of the it's incoming edge and increment flow by the same value X of one of it's outcoming edges. Obviously, flow-in = flow-out rule will still hold.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh , thank you . I have been too blinded.

    → Reply