1
$\begingroup$

I am learning algorithms to solve Maximum Flow problem by reading the CLRS book and confused by the following figure:

figure 26.4

That is:

A flow in a residual network provides a roadmap for adding flow to the original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in the corresponding residual network $G_f$, we define $f \uparrow f'$, the augmentation of flow $f$ by $f'$, to be a function from $V \times V$ to $R$, defined by

$$(f \uparrow f')(u, v) = \begin{cases} f(u,v) + f'(u, v) - f'(v, u) & > \text{if (u,v) $\in$ E} \\ 0 & \text{otherwise} \end{cases}$$

How the flow network in (c), for example $(s, v_2)$ got the flow 12 ? If we follow the formula, it must have a flow 5: $8 + 5 - 8 = 5$

$\endgroup$
4
$\begingroup$

That's not what the formula gives you. As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$. Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s \to v_2 \to v_3 \to t$. In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.

$\endgroup$
3
$\begingroup$

It is explained in part (b) of the caption of Figure 26.4.

The residual network $G_f$ with augmenting path $p$ shaded; its residual capacity is $c_f(p)=c_f(v_2,v_3)=4$.

Since the capacity of path $p$ is 4 (not 5), we find a flow $f'$ in the residual network $G_f$ that is defined by $f'(s,v_2)=f'(v_2,v_3)=f'(v_3,t)=4$. So for the network flow $f\uparrow f'$ in (c), we have $$ (f\uparrow f')(v_2, v_3)=f(v_2,v_3)+f'(v_2,v_3) = 8+4=12.$$

$\endgroup$

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.