I am trying to work this max-flow, min-cut out for my finals, but Im really not sure I have got it, I would appreciate some assistance! I understand the theorm, I comes from ford-fulkerson, where the maximum capacity through a network is pushed in a number of steps. The minimal cut from s to t = max flow.
But this question is giving me a headache:
Assume x = 0 What is the maximal flow from s to t? I got 2
Assume x = 10 What is the maximal flow from s to t? I got 8
What is the maximal value of cut that separates s from t and does not cut any of the edges sa and bt? Explain why this value is the same as the value of the minimal cut when capacity x is very large.
Here I answer max cut that separates s from t = 2+x, because 2 is max cut when x=0.
Now here is where my brain starts to die...
Determine the minimal value of each of the following type of cuts.
- The minimal value of a cut that does not cut any of the edges sa and bt. I got 2+x
- The minimal value of cut that cut the edge sa but does not cut the edge bt. I got x+4
- The minimal value of cut that cut the edge bt but does not cut the edge sa. I got 2+x
- The minimal value of a cut that cut both the edge sa and bt. I got 4
Let f(x) denote the maximal flow from s to t expressed as a function of x. Sketch the graph of f(x) from 0 ≤ x ≤ 10 (the results from the above question can be used to help consider different cases) I dont even know where to start with this question :(
Has anyone got any suggestions to my attempt of these questions and a hint for the last question?