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.
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 going into 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.
- The actual outflow from a vertex cannot be larger than the inflow capacity.
Consider this network, where the weight represent the number of shirts that can be shipped from one location to another in a month:
Even though $350$350 $\left(200+50+100\right)$(200+50+100) 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.
- 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 $18$18 $\left(10+8\right)$(10+8) 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!
The max-flow min-cut theorem
Now that we know these two principles, we’re going to put them together in an interesting way. This is a far more complicated network of international airports, where the weights represent the maximum number of flights that can be scheduled between the two airports in a single day:
Suppose $23$23 flights leave from $SFO$SFO to $LAS$LAS, and $8$8 flights leave from $SFO$SFO to $SEA$SEA. How many flights will make it all the way through the network to $ATL$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):
We are going to use a special method to answer this question, and in order to use this method there must be both a single source and a single sink in the network, which is what we have here!
We are going to cut the network with a line, 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 do this, 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.
A cut with less marked crossings is more likely (but not guaranteed!) to have the minimum total capacity.
These are all cuts that have $2$2 crossings from the source side to 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.
The numbers give us the total weights of the edges flowing across the cut from the source to the sink.
The least value obtained after considering each cut, in this case $26$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$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.
To find the maximum flow through a flow network, we:
- Draw in some cuts, marking 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?” It is a procedure that is relatively easy to both describe and apply. It has been used in a wide variety of applications from transport and shipping, to plumbing and architectural safety.
Practice questions
Question 1
Consider the flow network below.
Which vertex is the source for this flow network?
Which vertex is the sink for this flow network?
Question 2
Which of the cuts shown on the network are valid?
Select all the correct options.
$C1$C1
A$C2$C2
B$C3$C3
C$C4$C4
D$C5$C5
E
Question 3
Find the maximum flow through the following graph using the max-flow min-cut theorem or otherwise.
