topic badge

7.04 Maximum flow and minimum cut

Worksheet
Flow networks
1

For each of the flow networks below:

i

Name the vertex that is the source.

ii

Name the vertex that is the sink.

a
b
Maximum flow
2

For each of the following flow networks, calculate the inflow, outflow and maximum flow for the indicated vertices:

a

For vertices 2,3, \text{and } 4

b

For vertices 2,3, 4,\text{and } 5

Max-flow/min-cut theorem
3

For each of the following networks, list all the cuts that are valid:

a
b
c
4

For each of the following networks, calculate the capacity through each cut:

a
b
5

For each of the following flow networks:

i

Identify all the cuts shown on the network that are valid.

ii

Calculate the capacity through each of the valid cuts.

a
b
6

For each of the following networks, determine which of the cuts has the smallest capacity:

a
b
7

In each network, the source is the smallest numbered vertex and the sink is the largest numbered. For each of the following networks:

i
Calculate the maximum flow from the source.
ii
Calculate the maximum flow into the sink.
iii
By calculating the remaining cuts between the source and sink, determine the maximum flow for the network.
a
b
c
Applications
8

An oil company just received their pipe maps from the engineer connecting the oil storage tank (vertex 1) to its sink (vertex 7).

a

Calculate the maximum flow from the source.

b

Calculate the maximum flow into the sink.

c

By calculating the remaining cuts between the source and sink, determine the maximum flow of oil (in litres/hour) through the pipes.

9

The ventilation system of an apartment is being drafted by the engineer. The following graph represents the ducts and the maximum flow (in litres/second) in each one.

a

Calculate the maximum flow from the source (vertex A).

b

Calculate the maximum flow into the sink (vertex G).

c

By calculating the remaining cuts between the source and sink, determine the maximum flow (in litres/second) through the system.

10

An engineer was given the task to study the rainwater drainage in a certain area. The following graph represents the drains and their maximum capacity.

a

Calculate the maximum flow from the source (vertex 1).

b

Calculate the maximum flow into the sink (vertex 6).

c

By calculating the remaining cuts between the source and sink, determine the maximum flow of rainwater (in litres/hour) in the drainage system.

11

The following graph represents the road map between Balgownie and Kanahooka, and the maximum number of motorists that can travel on each road at one time.

a

Calculate the maximum number of vehicles that can travel from Balgownie to Kanahooka at a time.

b

How could the flow of traffic from Balgownie to Kanahooka be improved to cater for the following issues:

i

Unanderra is currently over supplied.

ii

Wollongong is currently under supplied.

iii

Port Kembla is currently over supplied.

iv

Fairy Meadow is currently under supplied.

12

A circuit involving a capacitor, three resistors and two inputs is represented by the following network, with the currents given in \text{mA}:

a

Calculate the maximum current that can flow between Power in and Power out.

b

Comment on anything you notice about the capacity through various cuts in this network.

13

The traffic flow (in hundreds of cars per hour) through a city centre is shown in the following directed network:

a

Identify the source vertex.

b

Identify the sink vertex.

c

Calculate the maximum flow from the source.

d

Calculate the maximum flow into the sink.

e

Calculate the maximum flow through this network.

14

A network of water pipes is shown in the first figure, with the maximum flow capacity of each pipe given in litres per minute. The second figure shows a possible flow of water within the network:

a

Determine the missing values in the second figure.

b

For the flow shown in second diagram, which pipes are operating at full capacity?

c

Calculate the total flow for the second diagram.

d

It is possible to increase the flow from part (c) by 5 \text{ litres/min}. State the path that can support this extra flow.

e

Determine the flow through each of the cuts P, Q, R and S in the diagram on the right.

f

State the cut that shows the flow achieved in part (d) is a maximum for this network.

15

The network below shows maximum electrical current (in \text{Amps}) that can flow from S to T through a system of conductors in an electrical circuit:

a
i

Calculate the capacity of SUT.

ii

Update the available capacity on the network.

b
i

Calculate the capacity of SVUT.

ii

Update the available capacity on the network.

c
i

Calculate the capacity of SVT.

ii

Update the available capacity on the network.

d
i

Calculate the capacity of SWXT.

ii

Update the available capacity on the network.

e
i

Calculate the maximum current for this circuit.

ii

State the cut that verifies this maximum current from the given diagram.

f

Annotate the network to show the current that should flow through each conductor in order to achieve the maximum capacity.

g

If the maximum current is flowing from S to T, calculate the current flowing through V.

h

If the current through V must be limited to 53\text{ Amps}, what conductor should be increased by the least amount to maintain the maximum capacity from S to T found in part (e).

16

Consider the following network:

a
i

Calculate the capacity of SAT.

ii

Update the available capacity on the network.

b
i

Calculate the capacity of SACT.

ii

Update the available capacity on the network.

c
i

Calculate the capacity of SBCT.

ii

Update the available capacity on the network.

d
i

Calculate the capacity of SBET.

ii

Update the available capacity on the network.

e

Calculate the maximum flow of this network.

f

Calculate the additional capacity that could be achieved with the addition of an edge from D to T.

g

In the original network, if the connection from S to B is removed, determine the capacity lost.

17

Consider the following network:

a
i

Calculate the capacity of SAET.

ii

Update the available capacity on the network.

b
i

Calculate the capacity of SBCDT.

ii

Update the available capacity on the network.

c
i

Calculate the capacity of SBCFT.

ii

Update the available capacity on the network.

d
i

Calculate the capacity of SFT.

ii

Update the available capacity on the network.

e

Calculate the max flow of this network.

f

The capacity of one edge is to be increased in order to increase flow through the network.

i

State which road should be chosen to maximise the increased flow.

ii

Calcuate the amount by which the flow is increased.

18

Calculate the maximum flow of the following network:

Sign up to access Worksheet
Get full access to our content with a Mathspace account

Outcomes

4.3.3.1

solve small-scale network flow problems including the use of the ‘maximum-flow minimum-cut’ theorem, e.g. determining the maximum volume of oil that can flow through a network of pipes from an oil storage tank to a terminal

What is Mathspace

About Mathspace