# Maximal flow problem: ford-fulkerson algorithm

1. May 10, 2017

### binbagsss

1. The problem statement, all variables and given/known data

Question attached:

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. May 10, 2017

### haruspex

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.

3. May 10, 2017

### Ray Vickson

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
4. May 11, 2017

### binbagsss

because the route of maximum flow is given by the cut of minimum capacity?

5. May 11, 2017

### Ray Vickson

In part, yes. Does adding the new arc change the min cut?

Last edited: May 12, 2017
6. May 11, 2017

### binbagsss

is that in part sorry?

yes I agree, to see whether it changes the minimal cut or not I need to do part a

7. May 12, 2017

### Ray Vickson

Typo fixed above.