A flow in a digraph with source and sink is a function such that where (the flow out of ) and (the flow into ). Convenient to set if .
is the directed edge from to . Loops and multiple edges are forbidden, so certainly or .
We imagine as representing a flow of water or electricity in a network, being pumped in at , and being pumped out at . The condition expresses that flow is conserved at each vertex.
is called the value of the flow where is the source and is the sink.
Let with and . Let . The net flow from to is .
Since we get .
Given a capacity function we require that for all .
Let with and . Let . The set of edges is called a cut with capacity .
For any cut we have .
The maximum value of a flow (source and sink ) in a network is equal to the minimum cut capacity.
If then there is a sequence of vertices starting with where for each either or . Let . We construct a new flow equal to except on the path but with or as appropriate. is a flow. so was not maximal, contradiction.
Algorithm increases. Take a subsequence monotonic on each edge. Take the limit. This flow has value of limit so it is maximal.
If . Let . is a cut. For every with and we have . For every edge , we have . . That is, the value of the flow is the cut capacity of some cut.
In a network with integer valued edge capacities there is a maximal flow whose value is equal to the minimum cut capacity, which has integer values at each edge.
Note that there may be a maximal flow which is not integer valued on each edge.
Consider multiple sources and multiple sinks . The value of the flow is and a cut is where and .
In a multiple source network the maximum value of a flow is equal to the minimum cut capacity.
Apply MFMC. Note that any cut of finite capacity cannot touch edges or so cut can be applied to original graph.
We can consider vertex capacities instead of edge capacities. The capacity function is now and we want . A cut is now a set of vertices such that has no path. It has capacity .
The maximum value of a flow in a network with vertex capacities is equal to the minimum cut capacity.
John Fremlin 2010-02-17