Find a maximum flow $f$ and a minimum cut $K$ in the network $N$

enter image description here

The book tell me that the max $val(f)=6$ and $K=[X,\overline X]$ with $X=\{u,s\}$. I'm not sure I know how they obtain that result. should I increase the flow as the red value and follow the bold path, so I have the $val(f)=6$ . I know that if $f$ is the max flow then $val(f)= cap K$ so $c(K)=6$ thus $k=\{(s,t),(u,x)\}$ which lead to $X=\{u,s\}$. Am I correct?

  • $\begingroup$ Even after increasing the flow by $1$ along that top/red path, your flow value is $5$. Can you see another augmenting path? $\endgroup$ – Casteels Nov 17 '14 at 6:12
  • $\begingroup$ I thought my flow value is 6, because $f^+(u)=6$ , everything else just cancel out, right? I can also go the straigth line $u-x-y-v$, but this path is not the maximum, right? $\endgroup$ – Diane Vanderwaif Nov 17 '14 at 12:23
  • $\begingroup$ The flow value is $f^+(u)-f^-(u)$, that is, the total flow leaving $u$ minus the total flow entering $u$. In this case, after pushing one unit of flow along the red path, you have $6$ units of flow leaving $u$ but you also have $1$ coming in, giving your flow a value of $5$. Do you know what an augmenting path is? $\endgroup$ – Casteels Nov 17 '14 at 12:34
  • $\begingroup$ oh, I for got 1 coming in. On my book there is definition for augmenting semi path. But I don't really understand it. If you could give me another definition of augmenting path, I would be very appreciated $\endgroup$ – Diane Vanderwaif Nov 17 '14 at 12:48
  • $\begingroup$ oh, so augmented path is the path that use to improve the flow, but how can I use it in this graph $\endgroup$ – Diane Vanderwaif Nov 17 '14 at 14:15

First, the flow value of the current flow is the net flow at $u$, that is, the total out minus the total in. (Equivalently, it is the total into $v$ minus the total out of $v$.) In your example, after you've pushed that one unit of flow along the top/red path, your total flow is $5$ ($6$ units out of $u$ minus $1$ unit into $u$).

A natural question is how do you know that your current flow is maximum? For this, you need to try to find augmenting paths. Suppose you have a path from $u$ to $v$ and you travel along that path starting at $u$. The path is called an augmenting path if for every edge on the path, the following hold:

  1. If the edge's direction agrees with the direction you are going in, then the flow value of that edge is not at capacity.
  2. If the edge's direction goes against your direction of travel, then that edge has a positive flow value on it.

A common mistake is to only look for paths from $u$ to $v$ where each edge agrees with the direction of travel. These can be augmenting paths (as your red path is, for example), but you also need to consider other possibilities. In your example, $(u,w,v)$ is an augmenting path since edge $(u,v)$ goes against your direction of travel but has positive flow value, and the edge $(w,v)$ agrees with your direction of travel but the flow value is less than capacity.

The point of an augmenting path is that you can "push" more flow from $u$ to $v$ along that path by some amount, where you lessen the flow along the edges that disagree with your direction of travel and you increase the flow along the edges that do agree with your direction. Of course you want to push as much flow as possible, and if you do this, your path will no longer be augmenting. In your example, you can push a maximum of one unit of flow along the augmenting path $(u,w,v)$ and the new flow value on $(u,w)$ is "$3,(0)$" and the new flow value on edge $(w,v)$ is "$5,(2)$".

The theorem you may have seen is:

A $(u,v)$-flow is maximum if and only if there are no augmenting paths from $u$ to $v$.

Now notice that your flow value is $6$, and you can check that there are no more augmenting paths, so your flow is maximum.

  • $\begingroup$ thank you very much, I think I understand it now $\endgroup$ – Diane Vanderwaif Nov 17 '14 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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