Australian Curriculum 12 General Mathematics - 2020 Edition

7.04 Maximum flow and minimum cut

Lesson

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 represents 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. We say the maximum flow is $120$120 shirts.

**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! We say the **maximum flow** is $5$5 students.

Consider the flow network below.

Which vertex is the source for this flow network?

Which vertex is the sink for this flow network?

Consider the following flow network.

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

Vertex Inflow Outflow $2$2 $\editable{}$ $\editable{}$ $3$3 $\editable{}$ $\editable{}$ $4$4 $\editable{}$ $\editable{}$ Now determine the maximum flow through each vertex in the table below:

Vertex Maximum Flow $2$2 $\editable{}$ $3$3 $\editable{}$ $4$4 $\editable{}$

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 $PER$`P``E``R` (Perth); and, there is one vertex where the edges only come in - so the sink for this network is $SYD$`S``Y``D` (Sydney).

*In this network, $PER$ PER is the source, and $SYD$SYD is the sink. *

We want to determine the maximum number of flights that could get us from $PER$`P``E``R` to $SYD$`S``Y``D`. 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 $PER-ADL-MEL-SYD$`P``E``R`−`A``D``L`−`M``E``L`−`S``Y``D` shown below:

The number of flights from $PER$`P``E``R` to $SYD$`S``Y``D` using this path is limited by the number of flights between $ADL$`A``D``L` and $MEL$`M``E``L`. So this path can contribute $5$5 flights to the total flow. We will record the capacity of each path in a table so that we can easily find the total.

Path | Capacity |
---|---|

$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD |
$5$5 |

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

The new weight for the edge from $ADL$`A``D``L` to $MEL$`M``E``L` is now zero, indicating that this link has no spare capacity. No more paths can use this edge.

Next, we consider the path through $PER-ADL-OOL-MEL-SYD$`P``E``R`−`A``D``L`−`O``O``L`−`M``E``L`−`S``Y``D`:

This path is limited by the capacity from $ADL$`A``D``L` to $OOL$`O``O``L`, with just $1$1 flight. So subtract $1$1 from the weight on each edge that is involved, and record $1$1 flight for this path in our table:

Path | Capacity |
---|---|

$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD |
$5$5 |

$PER-ADL-OOL-MEL-SYD$PER−ADL−OOL−MEL−SYD |
$1$1 |

Next, we consider the path through $PER-ADL-CAN-SYD$`P``E``R`−`A``D``L`−`C``A``N`−`S``Y``D`:

The capacity of this path is limited by the $1$1 remaining flight on the $PER-ADL$`P``E``R`−`A``D``L` edge, so we record $1$1 for this path and subtract $1$1 from the weights for all of the edges in this path.

Path | Capacity |
---|---|

$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD |
$5$5 |

$PER-ADL-OOL-MEL-SYD$PER−ADL−OOL−MEL−SYD |
$1$1 |

$PER-ADL-CAN-SYD$PER−ADL−CAN−SYD |
$1$1 |

Now, we consider the path through $PER-OOL-MEL-SYD$`P``E``R`−`O``O``L`−`M``E``L`−`S``Y``D`:

This path is limited to $2$2 flights, which is recorded in our table. After updating weights in the network, 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:

Path | Capacity |
---|---|

$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD |
$5$5 |

$PER-ADL-OOL-MEL-SYD$PER−ADL−OOL−MEL−SYD |
$1$1 |

$PER-ADL-CAN-SYD$PER−ADL−CAN−SYD |
$1$1 |

$PER-OOL-MEL-SYD$PER−OOL−MEL−SYD |
$2$2 |

Total |
$9$9 |

Using the suggested flight paths, there are a total of $9$9 flights between $PER$`P``E``R` and $SYD$`S``Y``D` each day.

Note that some edges are not fully utilised. For example, the edge from $MEL-CAN$`M``E``L`−`C``A``N` 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$10 flights from Perth to Sydney, which can be achieved by using the following paths in order:

Path | Capacity |
---|---|

$PER-ADL-CAN-SYD$PER−ADL−CAN−SYD |
$4$4 |

$PER-ADL-MEL-SYD$PER−ADL−MEL−SYD |
$3$3 |

$PER-OOL-MEL-SYD$PER−OOL−MEL−SYD |
$3$3 |

Total |
$10$10 |

For small networks and using some deduction this method can be useful to identify the maximum flow and edges with surplus or insufficient capacity.

Exhaustion of paths algorithm:

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

- Identify the
**source**and**sink**. - Working systematically (e.g. from top to bottom):

i) Select a path from source to sink.

ii) The minimum edge weight on the selected path is the capacity of the path.

iii) Record the capacity, and subtract the capacity from the weight of each edge on the selected path to determine the remaining capacity.

3. When there are no more paths with non-zero capacity, add the recorded capacity of each path. This is a possible flow through the network which may be the maximum flow.

Edges with zero weight after this process are fully utilised and have no spare capacity.

Caution

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, *$SFO$`S``F``O`* is the source and *$ATL$`A``T``L`* is the sink.*

Suppose the maximum possible number of flights leave $SFO$`S``F``O`, how many flights will make it all the way through the network to $ATL$`A``T``L`?

Let's consider the amount of flights that can leave our source at $SFO$`S``F``O` and the amount of flights that can land at our sink $ATL$`A``T``L`.

Drawing a **cut **across the edges leaving the source we can see there is a maximum of $31$31 flights that can leave $SFO$`S``F``O`. Similarly, drawing a cut across the edges entering the sink, we see there is a maximum of $27$27 flights that can land at $ATL$`A``T``L`. Since we can't send out more flights than can land we now know that the maximum capacity can be no more than $27$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:

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

Maximum-flow minimum-cut summary

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

This video goes through some very thorough examples that will help us to understand how to use the max-flow, min-cut theorem.

Consider the following flow network.

Which of the cuts shown on the network are valid?

Select all the correct options.

$C1$

`C`1A$C2$

`C`2B$C3$

`C`3C$C4$

`C`4D$C5$

`C`5E$C6$

`C`6F$C1$

`C`1A$C2$

`C`2B$C3$

`C`3C$C4$

`C`4D$C5$

`C`5E$C6$

`C`6FNow 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$ `C`2$\editable{}$ $C3$ `C`3$\editable{}$ $C5$ `C`5$\editable{}$

Find the maximum flow through the following graph using the max-flow min-cut theorem or otherwise.

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.

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

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

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.

AWollongong 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 Wollongong.

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

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

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

EFairy Meadow 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 Fairy Meadow.

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

AWollongong 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 Wollongong.

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

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

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

EFairy Meadow 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 Fairy Meadow.

F

solve small-scale network flow problems including the use of the ‘maximum-flow minimum- cut’ theorem; for example, determining the maximum volume of oil that can flow through a network of pipes from an oil storage tank (the source) to a terminal (the sink)