Maximal flow problem: ford-fulkerson algorithm

[binbagsss]

Homework Statement

Question attached:

Homework Equations

see below

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.

 

[haruspex]

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.

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.

 

[Ray Vickson]

Homework Statement

Question attached:View attachment 203334

Homework Equations

see below

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.

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.

 

[binbagsss]

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. .

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

 

[Ray Vickson]

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

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

 

[binbagsss]

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

is that in part sorry?

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

 

[Ray Vickson]

is that in part sorry?

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

Typo fixed above.