19.3 Max-Flow Min-Cut
The main focus of this section is Maximum-Flow Minimum-Cut Theorem; however, we need to understand some basics before we get there, so we will start from the basics.
This section is all about flow diagram. A flow diagram is simply a directed network with weights, and it also has a source vertex and sink vertex. As an example, the following is a flow diagram in its simplest form:
This could be a flow of water where s is the source (tap) and 100 indicates the rate at which it flows, so it can be 100mL/s. What this is indicating is the capacity of the edge (i.e. the maximum flow it can take on due to limitation of the size of pipe in this case).
There may be a case where capacity is not fully utilized. Consider a flow diagram below:
Though the capacity of edge sA is 100, it will have a flow of 30 in it at any given point as the capacity of the edge after sA is 30. So, one thing to remember is that flow can be lower than or equal to the capacity for any given edge.
An edge is also called saturated when its capacity is equal to its flow, which happens with At in the case above. The following example explains a few more things you need to know about these flow diagrams.
What is the flow for each of the edges in the following flow diagram? Are any of the edges saturated? What is the inflow at sink and outflow at source?
Working out flow is an iterative process where you put down the initial value of flow for a given edge, and then change it as you consider the prior edges in the network.
The following is the updated flow diagram with flow of each edge in red:
Considering the top of the diagram, sA has a capacity of 50, so 50 will pass through it, which will make AC flow 50 too even though it has a capacity of 60, while the same 50 will go to Ct.
Now Ct can take further 20 at most, which will make flow of sC 20.
(Note that it could have been the case where flow of sC stays at 30 and flow of sA, and in that case, AC will be 40 or any other combinations that make up 70. The important thing is that Ct will be 70, which dictates the sum of the flow that comes into node C.)
For the bottom of the diagram, even though sB has a capacity of 70 and BD has a capacity of 90, the capacity of Dt is 40, which will also make flow of the other two edges 40.
Regarding the question about which edges are saturated, it is the edges where capacity and flow are equal so Ct, Dt and sA.
Total inflow at t is 40 + 70 = 110, and total outflow at s is 50 + 20 + 40 = 110.
Before moving on to Max-flow Min-cut theorem, lets first look at the problem this theorem solves.
Suppose you have a connection of pipes flowing water from source to sink, and you must break that connection between source and sink for any reason, such as maintenance or changing pipes etc.
There are two things you want to achieve here. First, you want to make sure that the cuts you are making take you the least effort; you don’t want to cut the pipes that are bigger but you would rather cut smaller capacity pipes if they end up having the same effect because the smaller ones take less effort.
You also want to make sure that your cuts do the job of breaking the maximum flow from source to sink. Max-flow Min-Cut theorem is all about figuring out this very cut; hence the name.
Before talking about the theorem, it is important to understand what is defined as a cut in a flow.
The following flow diagram is cut by the red line. Determine if the cut is valid, identify the edges on the cut, and determine the capacity of the cut.
For a cut to be valid, the connection between source and sink should be cut; this happens in this case, as there is no way for the flow to pass from source to sink. Therefore, the cut is valid.
Edges on the red line are sB, BA and AC. Note that BA starts from sink side of the cut (right side of cut) and ends up on source side, which is against the definition for inclusion of edge in the cut; therefore, BA is not part of the cut.
sB and AC are part of the cut, and the cut capacity is capacity of these 2 edges, which is 70 + 60 = 130.
Max-flow Min-cut theorem says that any given cut whose capacity equals to its flow is the point where exists the maximum flow of the network and the minimum cut.
Let’s see the process in action.
Consider following flow diagram. Determine Max-flow Min-cut.
Let’s follow our steps:
- The following is a diagram redrawn with flow added for each edge:
- Saturated edges are sA and Dt
- Total inflow to sink is 50 + 40 = 90
- Max-flow Min-cut is through sA and Dt as shown below:
If you cut this flow diagram in any other way, it won’t be efficient. E.g. if you cut AC and BD, you will cut the same flow of 90, but the amount of capacity to cut will be 60 + 90 = 150 which is higher and requires more effort to cut than the capacity of 50 + 40 = 90 cut in the diagram above.
Get access to 20 Mock Exams with over 700 exam-style questions for HSC Standard Maths.
Click here to check them out!!