Introduction
In this lesson we will discuss a type of network called a flow network, and a theorem related to flow networks called the max-flow min-cut theorem. The following video presents these same ideas using different examples.
Ideas
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 of flow networks:
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. The outflow (the number of shirts being shipped to the three cities) can never be larger than 120, the inflow capacity.
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.
To find the maximum flow through a flow network using the minimum cut method, we:
Draw in some cuts, separating the network into two parts one containing the source, and one containing the sink.
Mark edges that cross from the source side to the sink side.
Add up the outflow capacity of the marked edges, making a note of the smallest total as we go.
Check other cuts to see if we can get a smaller value.
The maximum flow through the network is then equal to the capacity of the minimum cut. This is called 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?”. Flow networks have a wide variety of applications including scheduling, reliability frameworks, traffic flow, system flows for systems including electricity, water, gas and data. Calculating flow through a network has been used in a wide variety of applications from transport and shipping, to plumbing and architectural safety.
Now that we know these two principles, we’re going to put them together in an interesting way.
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:
Suppose 23 flights leave from \text{SFO} to \text{LAS}, and 8 flights leave from \text{SFO} to \text{SEA}. How many flights will make it all the way through the network to \text{ATL}?
Notice that there is one vertex where edges only come out (the source), and a vertex where the edges only come in (the sink):
The following method can only be used when there is a single source and a single sink in the network.
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. There are many ways to cut the network to separate the source from the sink, and here are a few:
Each cut picks out some vertices to be on the “source” side of the line, and the rest are on the “sink” side.
By marking 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, has very special significance. It 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.
Examples
Example 1
Which of the cuts shown on the network are valid? Select all the correct options
Example 2
Find the maximum flow through the following graph using the max-flow min-cut theorem or otherwise.
A flow network shows the clear beginning (source) and the clear end (sink) of a directed network.
Inflow capacity is the total weight of edges arriving at a vertex while the outflow capacity is the total weight of edges leaving at a vertex.
The maximum flow through a vertex is equal to the lower number out of the inflow and outflow for that vertex.
To find the maximum flow through a flow network using the minimum cut method, we:
Draw in some cuts, separating the network into two parts one containing the source, and one containing the sink.
Mark edges that cross from the source side to the sink side.
Add up the outflow capacity of the marked edges, making a note of the smallest total as we go.
Check other cuts to see if we can get a smaller value.
The maximum flow through the network is then equal to the capacity of the minimum cut. This is called the max-flow min-cut theorem.