2
$\begingroup$

In CLRS 3'rd edition there is a Lemma 26.2 which states that:

Let $G=(V, E)$ be a flow network, let $f$ be a flow in $G,$ and let $p$ be an augmenting path in $G_{f}$. Define a function $f_{p}\colon V \times V \rightarrow \mathbb{R}$ by $$f_{p}(u, v)=\left\{\begin{array}{ll}c_{f}(p) & \text { if }(u, v) \text { is on } p \\ 0 & \text { otherwise }\end{array}\right.$$ Then, $f_{p}$ is a flow in $G_{f}$ with value $\left|f_{p}\right|=c_{f}(p)>0$

How would you go about proving this?

As I understand we need to check for flow conservation and capacity constraint. We know that $c_f(p)$ is the minimum of the residual capacities on path $p$ which is smaller than the capacities, hence the capacity constraint is satisfied. But how about the flow conservation constraint and proving that the flow value is in fact $c_f(p) > 0$?

$\endgroup$
2
  • 2
    $\begingroup$ At a vertex $v$ the only non-zero terms in the condition of flow conservation are if $v$ is a vertex of $p$ and since $p$ is simple in that case there are only two terms. One term for the edge of $p$ that comes into $v$ and one for the edge of $p$ that leaves $v$. The condition reduces to $c_f(p)=c_f(p)$. The property $c_f(p)>0$ is a consequence of $p$ consisting of finitely many edges, all of positive capacity and $c_f(p)$ being the minimum of those finitely many positive numbers. $\endgroup$
    – plop
    Sep 4 '20 at 20:26
  • 1
    $\begingroup$ @plop Make an answer? $\endgroup$ Sep 5 '20 at 6:02
2
$\begingroup$

Observe that if $v$ is not a vertex of $p$, then $f_p(u,v)=0$. When $v$ is in $p$ and not a source nor a sink, then there are only two vertices $v_1$ and $v_2$ such that the edges $(v_1,v),(v,v_2)$ are in $p$. Therefore, in the excess flow at $v$ $$\sum_u f_p(u,v)$$ only has two non-zero terms $f_p(v_1,v)=c_f(p)$ and $f_p(v_2,v)=-f_p(v,v_2)=-c_f(p)$.

So, the excess flow is zero.

To see that $c_f(p)>0$ just recall that it is defined as the minimum of the residual capacities of the edges of $p$. There are finitely many edges in $p$ and by definition of augmenting path the residual capacities of its edges are positive. So, you are taking the minimum of finitely many positive numbers. That results in a positive number.

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