Scribd
Upload
9 views

04 Network Flows

The document discusses network flows, illustrating how to model networks with maximum and minimum capacities for edges. It explains the concept of cuts to determine maximum flow and introduces the idea of super sources and sinks for networks with multiple entry and exit points. Exercises and answers are provided to reinforce the concepts of finding flows and calculating maximum flow through various network scenarios.

Uploaded by

Fatima Muhaimin
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

04 Network Flows

The document discusses network flows, illustrating how to model networks with maximum and minimum capacities for edges. It explains the concept of cuts to determine maximum flow and introduces the idea of super sources and sinks for networks with multiple entry and exit points. Exercises and answers are provided to reinforce the concepts of finding flows and calculating maximum flow through various network scenarios.

Uploaded by

Fatima Muhaimin
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Modelling

with Algorithms
4. Network Flows
Introduction

A network might represent a series of pipelines transporting oil or water, or a map of one-way streets
carrying cars. The network will have information about how much water (litres per second) or cars (cars
per minute) can fit through. The numbers on the edges represent the maximum capacities for each part of
the network.

The cars (or … and leave the


water) enter network at the
the network at the SINK (T).
SOURCE (S) ...

This means that


the edge SA
has a maximum
flow of 12.

1. What’s the most amount of cars that can flow along route SDCT?
2. What’s the most amount of cars that can flow along route SDCABT?

Minimum Capacities

As well as indicating the maximum capacities of each edge, sometimes the network will have minimum
capacities for each edge. (In the network above all the minimum capacities are zero.)

This means that


the edge SA has a
minimum flow of 5,
and a maximum
flow of 12.

3. What’s the most amount of cars that can flow along route SABT?
4. What’s the least amount of cars that can flow along route SABT?
5. Fill in the table:
Route Maximum Flow Minimum Flow

SABT

SDCT
1
SDCABT
Cuts

The maximum flow through a network will be determines by the tightest bottleneck. To identify the tightest
bottleneck we can look at “cuts” through the network. A cut is a line through the network that separates
the source from the sink.

This is not a cut This is a cut


– S and T are on – S and T are
the same side of separated by
the line. the line.

The “value” of a cut represents the maximum flow that can cross at any one time. To find the value of a cut
add up all the maximum capacities of the edges that are crossing the cut forwards (from source side to sink
side) and subtract all the minimum capacities of the edges that are crossing the cut backwards (from sink
side to source side).

Add Subtract
Minimum capacities of edges
Value of a cut = Maximum capacities of edges crossing the cut backwards
crossing the cut forwards (from sink side to source side).
(from source side to sink side). This will be zero, if only
maximum capacities are shown.

6. Work out the values of these cuts:

2
Maximum Flow

Maximum Flow = Minimum Cut

In this example the minimum cut (= maximum flow) is 20.

7. Can you allocate flows to each of the edges so that there is a total flow of 20 through the network?

Super Source and Super Sink

If there are more than one source, you can add dummy edges leading from a “super source”. Each dummy
edge should have a maximum capacity at least as much as the sum of the edges it leads onto. You can do
the same thing to create a “super sink” if there are more than one sink.

3
Exercise

1. Finding Flows 1

2. Finding Flows 2

4
3. Basic Cuts and Flows

4. Mountain Lakes

5
5. Reservoir

6. Warehouses

6
7. Describing Cuts with Letters: SB-ACT

8. Describing Cuts with Letters: SC-ABT

7
9. Corridors

10. Passport Control

8
11. Playground

12. Upper and Lower Capacities 1

9
13. Upper and Lower Capacities 2

14. Upper and Lower Capacities 3

10
15. Upper and Lower Capacities 4

16. Upper and Lower Capacities 5

11
17. Blocked Edges

Answers
1. 8, 5, 11
2. 100
3. (a) (i) 45 million barrels
(ii) max flow ≤ 45 (b) 10, 14, 9
4. (a) see diagram
(b) (i) 40 (ii) max flow ≤ 40 (b) 8, 4
5. see diagram
6. (a) see diagram (b) 10, 8
7. (i) 18 – 0 + 10 + 3 + 5 = 36 4. 5.
(ii) 30, 32, 36 (iii) 29, max flow = min cut
(iv) see diagram

8. (i) 38 + 25 – 0 – 0 + 34 = 97
(ii) 65, 57, 72, 56 (iii) 53, max flow = min
cut (iv) see diagram
9. (a) 91 (b) 16, 18, 20
10. (a) R, U (b) 155 (c) 17, 31
11. (a) D (b) 25 + 17 + 35 + 13 + 12 + 13 = 6. 17.
115 (c) 25, 12
12. (a) 39 (b) 12, 7
13. (a) 26 (b) max flow ≤ 26 (c) 9, 5, 12, 4
14. (a) 44 (b) max flow ≤ 44 (c) 7, 10, 17
15. (a) 52 (b) 9, 5, 4
16. (a) 30 (b) 2, 3, 12
17. (a) 60, 80 (b) see diagram (c) (i) 45 7. 8.
(ii) cut through EH, EG, DG, DF, DC, AC
12

You might also like