Question

2. By summing an appropriate set of equations show that the capacity of a cut is at least as large as the value of a flow.

Answer 1

The Capacity is maxflow and mincut

In every flow network with source s and target t, the value of the maximum (s, t)-flow is equal to the capacity of the minimum (s, t)-cut.

in every flow network, there is a feasible (s, t)-flow f and an (s, t)- cut (S, T) such that |f | = kS, Tk. This is the famous Maxflow-Mincut Theorem, first proved by Lester Ford (of shortest-path fame) and Delbert Fulkerson in and independently by Peter Elias, Amiel Feinstein, and Claude Shannon (of information-theory and maze-solving-robot fame) in 1956.

Ford and Fulkerson proved this theorem as follows. Fix a graph G, vertices s and t, and a capacity function c: E ! R0. The proof will be easier if we assume that G is reduced, meaning there is at most one edge between any two vertices u and v. In particular, either c(uv) = 0 or c(vu) = 0. This assumption is easy to enforce: Subdivide each edge uv in G with a new vertex x, replacing uv with a path uxv, and define c(ux) = c(xv) = c(uv).

Let f be an arbitrary feasible (s, t)-flow in G. We define a new capacity function cf : V* V ⇥ R, called the residual capacity, as follows:

cf (uv) = c(uv) f (uv) if uv E

cf (uv) = f (vu)   if vu E

cf (uv) = 0    otherwise

Intuitively, the residual capacity of an edge indicates how much more flow can be pushed through that edge. Because f >=0and f <= c, these residual capacities are always non-negative. It is possible to have cf (uv) > 0 even if uv is not an edge in the original graph G. Thus, we define the residual graph Gf = (V, Ef ), where Ef is the set of edges whose residual capacity is positive. Most residual graphs are not reduced; in particular, if 0 < f (uv) < c(uv), then the residual graph Gf contains both uv and its reversal vu.

Now we have two cases to consider: Either there is a directed path from the source vertex s to the target vertex t in the residual graph Gf , or there isn’t.

First suppose the residual graph Gf contains a directed path P from s to t; we call P an augmenting path. Let F = min uv E P cf (uv) denote the maximum amount of flow that we can push through P. We define a new flow f ' : E arrow R (in the original graph) as follows:

f ' (uv) = f (uv) + F if uv E P

f ' (uv) = f (uv) F if vu E P

f ' (uv) = f (uv) otherwise

I claim that this new flow f ' is feasible with respect to the original capacities c, meaning f ' >=0 and f ' >= c everywhere. Consider an edge uv in the original graph G. There are three cases to consider.

• If the augmenting path P contains uv, then

f ' (uv) = f (uv) + F > f (uv) >=0

because f is feasible, and

f '  (uv) = f (uv) + F by definition of f '

<= f (uv) + cf (uv)   by definition of F

= f (uv) + c(uv) - f (uv) by definition of cf

= c(uv) Duh

• If the augmenting path P contains the reversed edge vu, then

f ' (uv) = f (uv) - F < f (uv) <= c(uv),

again because f is feasible, and

f ' (uv) = f (uv) - F by definition of f '

>= f (uv) - cf (vu)   by definition of F

= f (uv) - f (uv)   by definition of cf

=0 Duh

• Finally, if neither uv nor vu is in the augmenting path, then f '(uv) = f (uv), and therefore 0 <= f ' (uv) <= c(uv), because f is feasible.

So f is indeed feasible.

Finally, only the first edge in the augmenting path leaves s, which implies |f ' | = |f | + F > |f |. Thus, f ' is a feasible flow with larger value than f . We conclude that if there is a path from s to t in the residual graph Gf , then f is not a maximum flow.

On the other hand, suppose the residual graph Gf does not contain a directed path from s to t. Let S be the set of vertices that are reachable from s in Gf , and let T = V \ S. The partition (S, T) is clearly an (s, t)-cut. For every vertex u E S and v E T, we have

cf (uv)=(c(uv) - f (uv)) + f (vu) = 0.

The feasibility of f implies c(uv) - f (uv) >=0 and f (vu) >=0, so in fact we must have c(uv) - f (uv) = 0 and f (vu) = 0. In other words, our flow f saturates every edge from S to T and avoids every edge from T to S. Lemma now implies that |f | = IIS, TII, which means f is a maximum flow and (S, T) is a minimum cut.

This completes the proof!

Note : uv mens u arrow v , vu means v arrow u , E means euro sign.