Блог пользователя Pancake

Автор Pancake, 12 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.