A cut is minimal iff forward arcs saturated and reverse arcs flowless

2k Views Asked by At

Let $G = (V,A)$ be a network with arc capacity function $c$ and let $f$ be a flow on $G$. An arc $(x,y) \in A$ is said to be saturated if $f(x,y) = c(x,y)$ and flowless if $f(x,y) = 0$.

In Flows in Networks by Ford and Fulkerson it's stated without proof that that

Corollary 5.3. A cut $(X,\overline{X})$ is minimal if and only if every maximal flow $f$ saturates all arcs of $(X,\overline{X})$ whereas all arcs of $(\overline{X},X)$ are flowless with respect to $f$.

This is given as a corollary to the max-flow min-cut theorem. The backward ("if") direction of the corollary is clear to me, but why is the forward ("only if") direction true?

1

There are 1 best solutions below

0
On

I see now! If $f(x,y) < c(x,y)$ for some $(x,y) \in (X,\overline{X})$ or $f(x,y) = 0$ for some $(x,y) \in (\overline{X},X)$, then the value of the flow is less than the capacity of a cut. This contradicts the max-flow min-cut theorem. More precisely:

Let $F$ be the value of a maximal flow, $(X,\overline{X})$ a cut, and suppose $f(x,y) < c(x,y)$ for some $(x,y) \in (X,\overline{X})$. Then

$$F = \sum_{(x,y) \in (X,\overline{X})} f(x,y) - \sum_{(x,y) \in (\overline{X},X)} f(x,y) \le \sum_{(x,y) \in (X,\overline{X})} f(x,y) < \sum_{(x,y) \in (X,\overline{X})} c(x,y) = c(X,\overline{X}).$$

$(X,\overline{X})$ cannot be a minimal cut because $F \ne c(X,\overline{X})$. The $f(x,y) = 0$ case is similar.