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

Question

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

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?

Answer 1

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.