7.04 Maximum flow and minimum cut

Flow networks

Some directed networks have a clear beginning (called the source) and a clear end (called the sink). Such networks are flow networks. Each vertex has an amount of inflow capacity (total weight of all edges arriving at the vertex) and an outflow capacity (total weight of all edges leaving the vertex).

There are two principles to keep in mind when you’re thinking about flow networks.

1. The actual outflow from a vertex cannot be larger than the inflow capacity.

Consider this network, where the weight represents the number of shirts that can be shipped from one location to another in a month:

Even though $200+50+100=350$200+50+100=350 shirts can be shipped out of the warehouse in a month, only $120$120 can be shipped in. This means the outflow (the number of shirts being shipped to the three cities) can never be larger than $120$120, the inflow capacity. We say the maximum flow is $120$120 shirts.

2. The actual outflow from a vertex cannot be larger than the outflow capacity.

Consider this network, where the weights represent the number of students that can move from one place to another each minute:

Even though $10+8=18$10+8=18 students can join the lunch line every minute, only $5$5 can make it out to the cafeteria tables. If there were $7$7 students coming in from the playground and $9$9 from the oval in one particular minute, the inflow would be $7+9=16$7+9=16, but the outflow would be only $5$5 students - the line would just get longer!   We say the maximum flow is $5$5 students.

Practice questions

Question 1

Question 2

Possible flow through a network

Often we want to determine the maximum flow that is possible from a source to a sink in a flow network. A first step may be to consider possible flows through the network.  To do this, we need to work through the network systematically, considering the possible flow paths, and adding the total capacity for each path.

Exploration

Consider the network of Australian airports shown below.  The weights represent the maximum number of flights that can be scheduled between the airports each day.

Notice that there is one vertex where edges only come out - so the source for this network is $PER$PER (Perth);  and, there is one vertex where the edges only come in - so the sink for this network is $SYD$SYD (Sydney). 

In this network, $PER$PER is the source, and $SYD$SYD is the sink. 

We want to determine the maximum number of flights that could get us from $PER$PER to $SYD$SYD. Let's first look at a possible flow scenario. 

Finding a feasible number of flights requires identifying paths from source to sink, one-by-one, and working out the capacity of that path.

Once we have identified all paths, we can add the capacities to determine the total flow of the given scenario.

 

Working from the top-down, the first path that we select is $PER-ADL-MEL-SYD$PER−ADL−MEL−SYD shown below:

The number of flights from $PER$PER to $SYD$SYD using this path is limited by the number of flights between $ADL$ADL and $MEL$MEL.  So this path can contribute $5$5 flights to the total flow.  We will record the capacity of each path in a table so that we can easily find the total.

Path	Capacity
$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD	$5$5

Using the above flights has changed the available capacity for links between the airports that are involved, so we update the flow network weights, subtracting $5$5 from each weight. 

The new weight for the edge from $ADL$ADL to $MEL$MEL is now zero, indicating that this link has no spare capacity.  No more paths can use this edge.

 

Next, we consider the path through $PER-ADL-OOL-MEL-SYD$PER−ADL−OOL−MEL−SYD:

This path is limited by the capacity from $ADL$ADL to $OOL$OOL, with just $1$1 flight.  So subtract $1$1 from the weight on each edge that is involved, and record $1$1 flight for this path in our table:

Path	Capacity
$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD	$5$5
$PER-ADL-OOL-MEL-SYD$PER−ADL−OOL−MEL−SYD	$1$1

 

Next, we consider the path through $PER-ADL-CAN-SYD$PER−ADL−CAN−SYD: 

The capacity of this path is limited by the $1$1 remaining flight on the $PER-ADL$PER−ADL edge, so we record $1$1 for this path and subtract $1$1 from the weights for all of the edges in this path.

Path	Capacity
$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD	$5$5
$PER-ADL-OOL-MEL-SYD$PER−ADL−OOL−MEL−SYD	$1$1
$PER-ADL-CAN-SYD$PER−ADL−CAN−SYD	$1$1

 

Now, we consider the path through $PER-OOL-MEL-SYD$PER−OOL−MEL−SYD: 

This path is limited to $2$2 flights, which is recorded in our table.  After updating weights in the network, we can see that all paths are now blocked by an edge with a weight of zero. 

The zero weighted edges are being used at maximum capacity so we have now reached the maximum flow capacity for the chosen flight paths. 

We can now work out the total flow for the network using the suggested flight paths. Using the edge capacities recorded in our table:

Using the suggested flight paths, there are a total of $9$9 flights between $PER$PER and $SYD$SYD each day.

Note that some edges are not fully utilised.  For example, the edge from $MEL-CAN$MEL−CAN was not used at all.

Is this the maximum flow for the network?

While this method gives us a possible flow using several edges at their maximum capacity it may not give the overall maximum flow for the network. If we select paths from source to sink in a different order we may find a combination that utilises more capacity in the network. This is in fact the case in the scenario given above. The maximum flow of the given network is $10$10 flights from Perth to Sydney, which can be achieved by using the following paths in order:

For small networks and using some deduction this method can be useful to identify the maximum flow and edges with surplus or insufficient capacity.

Max-flow/min-cut theorem

We will now consider a method for determining the maximum flow through a network from source to sink.

Exploration

This network represents the connections between a number of international airports.  The weights represent the maximum number of flights that can be scheduled between the two airports in a single day:

In this network, $SFO$SFO is the source and $ATL$ATL is the sink.

Suppose the maximum possible number of flights leave $SFO$SFO, how many flights will make it all the way through the network to $ATL$ATL?

Let's consider the amount of flights that can leave our source at $SFO$SFO and the amount of flights that can land at our sink $ATL$ATL.

Drawing a cut across the edges leaving the source we can see there is a maximum of $31$31 flights that can leave $SFO$SFO. Similarly, drawing a cut across the edges entering the sink, we see there is a maximum of $27$27 flights that can land at $ATL$ATL. Since we can't send out more flights than can land we now know that the maximum capacity can be no more than $27$27 flights. But are there flight paths that restrict the flow further?

Each cut picks out some vertices to be on the “source” side of the line, and the rest are on the “sink” side. 

If we mark out every place where the edges cross the cut from the source part to the sink part, we get a diagram like this:

Not every crossing between edge and cut has been marked - only when the edge starts at a vertex on the source side and connects across the cut to a vertex on the sink side.
Two of the cuts have $2$2 markings, one has $3$3, and one has $5$5.

A cut with less marked crossings is more likely to have the minimum total capacity. So instead let's draw in some cuts with exactly $2$2 marked crossings on this network:

These are all cuts that have $2$2 crossings from the source side to the sink side.

We now add up the weights of the edges across these cuts:

The least value obtained after considering each cut, in this case $26$26. This is the minimum cut, and tells us the maximum flow through the network. For this example we have an answer to our question - at most $26$26 flights can make it from $SFO$SFO to $ATL$ATL in a single day.

To be sure, we should check all cuts, including those we marked earlier that have $3$3 or more marked crossings - in this case, no cut can improve on this result. To understand this intuitively, we know that at most $26$26 flights can cross the purple line in a single day, and all flights must pass through this line on their way from source to sink.

This theorem is an extremely useful idea, since it allows us to answer a big question - “what is the maximum flow through a network?” - with a procedure that is relatively easy to both describe and execute. It has been used in a wide variety of applications from transport and shipping, to plumbing and architectural safety.

This video goes through some very thorough examples that will help us to understand how to use the max-flow, min-cut theorem.

Practice questions

Question 3

Question 4

Question 5