Network Flow
Network Flow: Max-flow min-cut theorem
One interesting topic in the study of networks is measuring flow across networks. Suppose we have a directed network where each edge has a capacity function, c(e). This capacity represents the maximum amount that can flow through the edge. On this network there is a source, s, and a sink, t. Edges connected to the source are only directed away from the source and edges connected to the sink are only directed toward the sink.
This presents the problem of determining the maximum amount of flow that could leave the sink and get to the source. The max-flow min-cut theorem optimizes a solution to this problem. First we can define a cut to be a disjoint union of sub-networks of the network, X and Y where s is an element of X and t is an element of Y. The union of X and Y is the entire vertex set of the network, V(N). We want to examine the capacity along edges from X to Y. The sum of the capacities of these edges is the value of the capacity of the cut.
Finding the max-flow through a network can be very useful for studying trading in banking, optimizing transportation of electricity through power lines, and many other applications. By the max-flow min-cut theorem, the max-flow through a network is exactly equal to the minimum capacity of the set of all cuts of a network. We can see that the max-flow must be at most the min-cut because in order for flow to go from source to sink it must go through every cut meaning that it the capacity of the cut bounds the flow above. We can also see that the min-cut bounds below because if there were no flow that is maximized through this min-cut then there would have to be another min-cut.
- Network Flow Example
We can see that the min-cut along the graph is X = {s, A, C, D, E, F, G, H} and Y = {t, B}.
c(X,Y) = 20 so the max-flow must also be 20. Try to find the flow yourself.
Source: Lint, Jacobus Hendricus Van, and R. M. Wilson. A Course in Combinatorics. Cambridge, U.K.: Cambridge UP, 2001. Print.