maximum flow/minimum cut theorem


Let G be a finite digraphMathworldPlanetmath with nonnegative weights and with exactly one sink and exactly one source. Then

I) For any flow f on G and any cut C of G, the amount of flow for f is less than or equal to the weight of C.

II) There exists a flow f0 on G and a cut C0 of G such that the amount of the flow of f0 equals the weight of C0.

Proof: (I) is easy, so we prove only (II). Write + for the set of nonnegative real numbers. Let V be the set of vertices of G. Define a matrix

κ:V×V+

where κ(x,y) is the sum of the weights (or capacities) of all the directed edges from x to y. By hypothesisMathworldPlanetmathPlanetmath there is a unique vV (the source) such that

κ(x,v)=0  xV

and a unique wV (the sink) such that

κ(w,x)=0  xV.

We may also assume κ(x,x)=0 for all xV. Any flow f will correspond uniquely (see Remark below) to a matrix

φ:V×V+

such that

φ(x,y) κ(x,y)  x,yV
zφ(x,z) = zφ(z,x)  xv,w

Let λ be the matrix of any maximal flow, and let A be the set of xV such that there exists a finite sequencePlanetmathPlanetmath x0=v,x1,,xn=x such that for all m from 1 to n-1, we have either

λ(xm,xm+1)<κ(xm,xm+1) (1)

or

λ(xm+1,xm)>0. (2)

Write B=V-A.

Trivially, vA. Let us show that wB. Arguing by contradictionMathworldPlanetmathPlanetmath, suppose wA, and let (xm) be a sequence from v to w with the properties we just mentioned. Take a real number ϵ>0 such that

ϵ+λ(xm,xm+1)<κ(xm,xm+1)

for all the (finitely many) m for which (1) holds, and such that

λ(xm+1,xm)>ϵ

for all the m for which (2) holds. But now we can define a matrix μ with a larger flow than λ (larger by ϵ) by:

μ(xm,xm+1)=ϵ+λ(xm,xm+1)  if (1) holds
μ(xm+1,xm)=λ(xm+1,xm)-ϵ  if (2) holds
μ(a,b)=λ(a,b)  for all other pairs (a,b).

This contradiction shows that wB.

Now consider the set C of pairs (x,y) of vertices such that xV and yW. Since W is nonempty, C is a cut. But also, for any (x,y)C we have

λ(x,y)=κ(x,y) (3)

for otherwise we would have yV. Summing (3) over C, we see that the amount of the flow f is the capacity of C, QED.

Remark: We expressed the proof rather informally, because the terminology of graph theoryMathworldPlanetmath is not very well standardized and cannot all be found yet here at PlanetMath. Please feel free to suggest any revision you think worthwhile.

Title maximum flow/minimum cut theoremMathworldPlanetmath
Canonical name MaximumFlowminimumCutTheorem
Date of creation 2013-03-22 13:00:55
Last modified on 2013-03-22 13:00:55
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 12
Author bbukh (348)
Entry type Theorem
Classification msc 05C20
Synonym max flow min cut theorem
Related topic Flow
Related topic Cut
Related topic MaximalMatchingminimalEdgeCoveringTheorem