- #1
binbagsss
- 1,275
- 11
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.