 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

Calculate the maximum flow through the following networks:

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

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

Calculate the maximum flow between the source (vertex A) and the sink node (vertex G).

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.

Calculate the maximum flow of rainwater (in litres/hour) in the drainage system between vertex 1 and vertex 6.

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

Consider the flow capacity of the following network:

a
i

Calculate the capacity of SMNT.

ii

Update the available capacity on the network.

b
i

Calculate the capacity of SQMNT.

ii

Update the available capacity on the network.

c
i

Calculate the capacity of SQRNT.

ii

Update the available capacity on the network.

d
i

Calculate the capacity of SQRT.

ii

Update the available capacity on the network.

e

Calculate the maximum flow of this network.