1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximal flow problem: ford-fulkerson algorithm

  1. May 10, 2017 #1
    1. The problem statement, all variables and given/known data

    Question attached: ford-fulk part c.png

    2. Relevant equations

    see below

    3. The attempt at a solution

    - The theorem without prove i require needed is that the cut of maximum flow is given by the cut of minimal capacity.
    My proof would be along the lines of:
    - using this theorem, obviously 100 is a large capacity compared to the other values so i would perhaps justify this more explictly by :
    - computing how many distinct cuts there are, and summing the capacity of all of all to show that all cuts containing arc SE have a greater capacity.
    - as for a short-cut without needing to compute all distinct cuts, I'm not really sure how to prove to it, it appears that it should be pretty trivial given the theorem and the large capacity, but I'm unsure what to write down properly.

    Any help much appreciated.
     
  2. jcsd
  3. May 10, 2017 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I do not see how this argument is going to work. If adding an arc se with a capacity of 1 increases the flow then so will adding one of capacity 100.
    I would look at the max flow from s to e in the network as it is.
     
  4. May 10, 2017 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Have you solved the max-flow problem from part (a)? That would tell you the min-cut capacity, and then all you need to do is look for a cut having that capacity. There is no need to enumerate all the cuts (although that should also work, of course). You should think more about part (c): remember the max-flow, min-cut theorem.
     
    Last edited: May 11, 2017
  5. May 11, 2017 #4
    because the route of maximum flow is given by the cut of minimum capacity?
     
  6. May 11, 2017 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    In part, yes. Does adding the new arc change the min cut?
     
    Last edited: May 12, 2017
  7. May 11, 2017 #6
    is that in part sorry?

    yes I agree, to see whether it changes the minimal cut or not I need to do part a
     
  8. May 12, 2017 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Typo fixed above.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Maximal flow problem: ford-fulkerson algorithm
  1. Maximization problem (Replies: 7)

Loading...