7.04 Maximum flow and minimum cut

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 shirts can be shipped out of the warehouse in a month, only 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, the inflow capacity. We say the maximum flow is 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 students can join the lunch line every minute, only 5 can make it out to the cafeteria tables. If there were 7 students coming in from the playground and 9 from the oval in one particular minute, the inflow would be 7+9=16, but the outflow would be only 5 students - the line would just get longer. We say the maximum flow is 5 students.

Examples

Example 1

Consider the flow network below.

a

Which vertex is the source for this flow network?

Worked Solution

Create a strategy

Find the vertex where the edges are only moving out of it.

Apply the idea

3 edges are moving out of B and no edges are going into it.

The source is vertex B.

Watch question walkthrough

b

Which vertex is the sink for this flow network?

Worked Solution

Create a strategy

Find the vertex where edges are only moving into it..

Apply the idea

3 edges are pointing into vertex E and none are pointing out of it.

The sink is vertex E.

Watch question walkthrough

Example 2

Consider the following flow network.

a

Determine the inflow and outflow for the vertices in the table below:

Vertex	Inflow	Outflow
2
3
4

Worked Solution

Create a strategy

The inflow capacity is the weight of the edge pointing into the vertex while the outflow capacity is the weight of the edge pointing pointing out of the vertex.

Apply the idea

Vertex	Inflow	Outflow
2	15	20
3	10	35
4	30	10

Watch question walkthrough

b

Now determine the maximum flow through each vertex in the table below:

Vertex	Maximum Flow
2
3
4

Worked Solution

Create a strategy

The maximum flow is the lower number out of the inflow and outflow for each vertex.

Apply the idea

In each row of the table from part (a) choose the lower number.

Vertex	Maximum Flow
2	15
3	10
4	10

Watch question walkthrough

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.

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 \text{PER} (Perth); and, there is one vertex where the edges only come in - so the sink for this network is \text{SYD} (Sydney).

We want to determine the maximum number of flights that could get us from \text{PER} to \text{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 \text{PER$-$ADL$-$MEL$-$SYD} shown below:

The number of flights from \text{PER} to \text{SYD} using this path is limited by the number of flights between \text{ADL} and \text{MEL}, since this is the smallest weight along the path. So this path can contribute 5 flights to the total flow.

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 from each weight.

The new weight for the edge from \text{ADL} to \text{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 \text{PER $-$ ADL $-$ OOL $-$ MEL $-$ SYD}:

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

Next, we consider the path through \text{PER$-$ADL$-$CAN$-$SYD}:

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

Now, we consider the path through \text{PER$-$OOL$-$MEL$-$SYD}:

This path is limited to 2 flights, which is recorded in our table and subtracted from each weight along the path.

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 flights between \text{PER} and \text{SYD} each day.

Note that some edges are not fully utilised. For example, the edge from \text{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 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. This algorithm does not necessarily find the maximum flow of the network. Processing the possible paths in a different order may produce a higher overall flow.

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

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, \text{SFO} is the source and \text{ATL} is the sink.

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

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

Drawing a cut across the edges leaving the source we can see there is a maximum of 31 flights that can leave \text{SFO}. Similarly, drawing a cut across the edges entering the sink, we see there is a maximum of 27 flights that can land at \text{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 flights. But are there flight paths that restrict the flow further?

To see this will use a procedure where we cut the network with a line as we did above, drawing through the edges and separating the network into two parts - one containing the source, and one containing the sink. We can then calculate the maximum flow from source to sink across each cut. The overall network flow will be restricted to the minimum of these flows.

There are many ways to cut the network to separate the source from the sink, and here are a few:

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 markings, one has 3, and one has 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 marked crossings on this network:

These are all cuts that have 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. 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 flights can make it from \text{SFO }to \text{ATL }in a single day.

To be sure, we should check all cuts, including those we marked earlier that have 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 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 video goes through some very thorough examples that will help us to understand how to use the max-flow, min-cut theorem.

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.

Examples

Example 3

Consider the following flow network.

a

Which of the cuts shown on the network are valid? Select all the correct options.

A

C1

B

C2

C

C3

D

C4

E

C5

F

C6

Worked Solution

Create a strategy

Choose the cuts that divide the network into two where one part has the source and the other has the sink.

Apply the idea

The source is vertex 1 and the sink is vertex 9. So we need to choose cuts that have vertex 1 one one side and vertex 9 on the other.

Cuts C2, \, C3, and C5 divide the network into two where one part has the source and the other has the sink.

The answers are options B, C, and E.

b

Now determine the capacity through each of the valid cuts in the table below. Make sure to pay attention to the direction of each edge.

Cut	Capacity
C2
C3
C5

Worked Solution

Create a strategy

Add the weight of the edges passing from the source side to the sink side through each cut.

Apply the idea

\displaystyle C2	\displaystyle =	\displaystyle 9+35+11	Add the weight of the edges
	\displaystyle =	\displaystyle 55	Evaluate
\displaystyle C3	\displaystyle =	\displaystyle 14+32+27+11	Add the weight of the edges
	\displaystyle =	\displaystyle 84	Evaluate
\displaystyle C5	\displaystyle =	\displaystyle 14+23+25	Add the weight of the edges
	\displaystyle =	\displaystyle 62	Evaluate

Cut	Capacity
C2	55
C3	84
C5	62

Example 4

The following graph represents the road map between Balgownie and Kanahooka, and the maximum number of motorists that can travel on each road at a time.

a

What is the maximum number of vehicles that can travel from Balgownie to Kanahooka at a time?

Worked Solution

Create a strategy

Follow the steps using the max-flow min-cut theorem to find the minimum cut:

1. Draw in some cuts, marking edges that cross from the source side to the sink side.

2. Add up the outflow capacity of the marked edges, making a note of the smallest total as we go.

3. Check all other cuts to see if we can get a smaller value.

Apply the idea

The source if Balgownie and the sink is Kanahooka. Below are some cuts that separate the source and sink:

Now we will find the outflow capacity of each cut.

\displaystyle C1 \text{ outflow}	\displaystyle =	\displaystyle 161+133+145	Add the weights the cut intersects
	\displaystyle =	\displaystyle 439	Evaluate

\displaystyle C2 \text{ outflow}	\displaystyle =	\displaystyle 161+133+117+113	Add the weights the cut intersects
	\displaystyle =	\displaystyle 524	Evaluate

\displaystyle C3 \text{ outflow}	\displaystyle =	\displaystyle 161+140+112+129+113	Add the weights the cut intersects
	\displaystyle =	\displaystyle 655	Evaluate

\displaystyle C4 \text{ outflow}	\displaystyle =	\displaystyle 160+112+110	Add the weights the cut intersects
	\displaystyle =	\displaystyle 382	Evaluate

C4 has the smallest outflow, at 382, and so allows the smallest number of motorists through. We could try more cuts but it seems like we will not find a smaller one than this.

So the maximum number of vehicles that can travel from Balgownie to Kanahooka is 382.

Watch question walkthrough

b

What recommendations could you make to the transport authorities to improve the maximum flow of traffic from Balgownie to Kanahooka?

A

Unanderra is currently over supplied, so the flow could be improved by increasing the amount of traffic that can travel on the road from Unanderra to Kanahooka.

B

Wollongong is currently under suplied, so the flow could be improved by increasing the amount of traffic that can travel on the road from Balgownie to Wollongong.

C

Port Kembla is currently over supplied, so the flow could be improved by increasing the amount of traffic that can travel on the road from Port Kembla to Kanahooka.

D

Wollongong is currently over suplied, so the flow could be improved by increasing the amount of traffic that can travel on the road from Wollongong to Port Kembla.

E

Unanderra is currently under supplied, so the flow could be improved by increasing the amount of traffic that can travel on the road from Balgownie to Unanderra.

F

Fairy Meadow is currently under suplied, so the flow could be improved by increasing the amount of traffic that can travel on the road from Balgownie to Fairy Meadow.

Worked Solution

Create a strategy

If the inflow is higher than the outflow the vertex is over supplied.

If the outflow is higher than the inflow the vertex is under supplied.

Apply the idea

Unanderra has an inflow of 161 and an outflow of 160 toward Kanahooka, so it is oversupplied. This would be improved by increasing the amount of traffic that can travel on the road from Unanderra to Kanahooka.

Wollongong has an inflow of 133+117=250 and an outflow of 140+112+129=381 so it is under supplied. This would be improved by increasing the amount of traffic that can travel on the road from Balgownie to Wollongong.

Port Kembla has inflow of 129+113=242 and an outflow of 110 so it is oversupplied. This would be improved by increasing the amount of traffic that can travel on the road from Port Kembla to Kanahooka.

Fairy Meadow has inflow of 145 and an outflow of 117+113=230 so it is undersupplied. his would be improved by increasing the amount of traffic that can travel on the road from Balgownie to Fairy Meadow.

The correct recommendations are options A, B, C, and F.

Watch question walkthrough