Max flow min cut algorithm

Question

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.

1. The minimal value of a cut that does not cut any of the edges sa and bt. I got 2+x
2. The minimal value of cut that cut the edge sa but does not cut the edge bt. I got x+4
3. The minimal value of cut that cut the edge bt but does not cut the edge sa. I got 2+x
4. 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?

Answer 1

Assume x = 0 What is the maximal flow from s to t? I got 2

This is correct.

Assume x = 10 What is the maximal flow from s to t? I got 8

This is incorrect. The first flow-augmenting path chosen is $s \to a \to t$ which augments the flow by $4$.

I then choose $s \to a \to b \to t$ (pushing flow back across the incoming arc with capacity $2$), which augments the flow by $2$.

I then choose $s \to b \to t$, which augments the flow by $5$.

Finally, I choose $s \to a \to b \to t$, pushing flow across the outgoing arc with capacity $1$.

So you push flow of $12$ through the graph.

The minimal value of a cut that does not cut any of the edges sa and bt. I got 2+x

How did you get this? The value of a cut is the capacity of the arcs going from one partition to the other. So if sa and bt must be together, we have: $[\{s, a\}, \{b, t\}]$. So we have arcs $(s, a), (a, b), (a, t)$. The sum of the capacities of those arcs is the value of your cut.

The minimal value of cut that cut the edge sa but does not cut the edge bt. I got x+4

So our cut is $[\{s\}, \{a, b, t\}]$. So then $x + 5$ is the value of the cut.

Can you take it from here with the other two cuts?

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

Here is my hint. What happens when $x < 8$? What happens when $x > 8$? Consider how much flow you can push across the arc $(s, a)$ based on values of $x$.

Answer 2

ml0105 you are wrong.

when x = 10
The max flow is 10.

augmenting paths:

s-a-t --->+4

s-b-t --->+5

s-a-b-t--->+1

notice that (a,t) ,(a,b), (s,b) are now saturated and therefore max flow = 10. and the min cut is equal to {s,a}.

u can also check:

acording to visualgo (http://visualgo.net/maxflow.html), (u can draw any graph in visualgo)

when x = 10 the max flow = 10.