NZ Level 8 (NZC) Level 3 (NCEA) [In development]

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.

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.

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

**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!

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$`S``F``O` to $LAS$`L``A``S`, and $8$8 flights leave from $SFO$`S``F``O` to $SEA$`S``E``A`. How many flights will make it **all the way through** the network to $ATL$`A``T``L`?

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:

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:

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:

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$`S``F``O` to $ATL$`A``T``L` 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:

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

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

Use critical path analysis in solving problems