maximum flow/minimum cut theorem
Let be a finite digraph with nonnegative weights and with exactly one sink and exactly one source. Then
I) For any flow on and any cut of , the amount of flow for is less than or equal to the weight of .
II) There exists a flow on and a cut of such that the amount of the flow of equals the weight of .
Proof: (I) is easy, so we prove only (II). Write for the set of nonnegative real numbers. Let be the set of vertices of . Define a matrix
where is the sum of the weights (or capacities) of all the directed edges from to . By hypothesis there is a unique (the source) such that
and a unique (the sink) such that
We may also assume for all . Any flow will correspond uniquely (see Remark below) to a matrix
Let be the matrix of any maximal flow, and let be the set of such that there exists a finite sequence such that for all from to , we have either
for all the (finitely many) for which (1) holds, and such that
for all the for which (2) holds. But now we can define a matrix with a larger flow than (larger by ) by:
This contradiction shows that .
Now consider the set of pairs of vertices such that and . Since is nonempty, is a cut. But also, for any we have
Remark: We expressed the proof rather informally, because the terminology of graph theory 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 theorem|
|Date of creation||2013-03-22 13:00:55|
|Last modified on||2013-03-22 13:00:55|
|Last modified by||bbukh (348)|
|Synonym||max flow min cut theorem|