Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

enter image description here

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?

share|improve this question

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.