NZ Level 8 (NZC) Level 3 (NCEA) [In development]
topic badge
Network Flow
Lesson

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 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 represent 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.

  1. 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!

 

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 there is!

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. 

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, 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.

 

Recap

To find the maximum flow through a flow network, we:

  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 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?” - 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.

Outcomes

M8-5

Develop network diagrams to find optimal solutions, including critical paths.

91576

Use critical path analysis in solving problems

What is Mathspace

About Mathspace