Kourosh Davoudi

kourosh@[Link]

Lecture 12: Flow Graphs

CSCI 3070U: Design and Analysis of Algorithms

Learning Outcomes

• Flow Networks:
• Concepts and Foundations
• Algorithms

3
Flow Network

• A flow network G =(V, E) is a directed graph in which each edge

(u, v) ∈ E has a nonnegative capacity c(u, v) ≥ 0

4
Flow Network

• We distinguish two vertices in a flow network:

• Source s
• Sink t
• We assume that each vertex
lies on a path from source to sink

• For all v ∈ V , we have a path

5
Flow Networks Properties

• A flow network G =(V, E) is a directed graph in which each edge

u ∈ E has a nonnegative capacity c(u, v) ≥ 0

• If (u, v) ∈ E, then (v, u) ∉ E

• If (v, u) ∉ E, then c(v, u) = 0

6
Flow Definition

• Flow is a function satisfying:

• Capacity Constraint:

For all

• Flow Conservation:

For all

7
Value of Flow

• Value of flow f is defined as follows:

= flow out of source – flow into source

• Example:
=?

Answer = 3

8
Maximum Flow Problem

• Given G, s, t, and c, find a flow whose value is maximum

• Maximum rate of shipping product from Vancouver to Winnipeg through

intermediate cities

9
Antiparallel Edges

• Definition of flow network does not allow both (u, v) and (v, u) to be
edges. These edges would be antiparallel

• What if we really need antiparallel edges?

10
Networks with Multiple Sources and Sinks

11
Residual Network

• Given a flow f in network G = (V, E), the residual network of G is Gf

12
Augmenting Paths

• Given a flow network G = (V, E) and a flow f, an augmenting path p is a

simple path from s to t in the residual network Gf .
• A simple path is a path without cycle.

• How much more flow can we push from s to t along augmenting path p?

Residual Capacity
13
Augmenting Paths

• The shaded path is an augmenting path

Gf
Gf

= min{5, 4, 5} = 4

14
Augmenting Paths

• Insight: We can increase the flow through each edge of this path by up
to 4 units without violating the capacity constraint:

G with augmented flow

Gf based on path p

15
Ford-Fulkerson Algorithm

• Given G, s, t, and c, it finds a flow whose value is maximum

• General ideas:
• In each iteration of the Ford-Fulkerson method, we find some augmenting
path p and use p to modify the flow f
• That is, adding flow when the residual edge in p is an original edge and
subtracting it otherwise
• When no augmenting paths exist, the flow f is a maximum flow.

18
Ford-Fulkerson Algorithm Example
0/20
G Gf

Are there any augmenting path?

Gf New G

19
=4
Ford-Fulkerson Algorithm Example

G Gf

=4

New G 20
Ford-Fulkerson Algorithm Example

G Gf

=4

0/4

New G 21
Ford-Fulkerson Algorithm Example

G Gf

=7

New G 22
Ford-Fulkerson Algorithm Example

G Gf

=4

New G 23
Ford-Fulkerson Algorithm Example

G Gf

Answer = 23 No Augmenting Path !

24
Ford-Fulkerson Algorithm

25
Ford-Fulkerson Algorithm

O(E)
<latexit sha1_base64="ESo6+Z950D6YsnMcBLnofXXbgxE=">AAAB63icbVBNSwMxEJ2tX7V+VT16CRahXspuFdRbQQRvVrC20C4lm2bb0CS7JFmhLP0LXjwo4tU/5M1/Y7bdg7Y+GHi8N8PMvCDmTBvX/XYKK6tr6xvFzdLW9s7uXnn/4FFHiSK0RSIeqU6ANeVM0pZhhtNOrCgWAaftYHyd+e0nqjSL5IOZxNQXeChZyAg2mXRXvTntlytuzZ0BLRMvJxXI0eyXv3qDiCSCSkM41rrrubHxU6wMI5xOS71E0xiTMR7SrqUSC6r9dHbrFJ1YZYDCSNmSBs3U3xMpFlpPRGA7BTYjvehl4n9eNzHhpZ8yGSeGSjJfFCYcmQhlj6MBU5QYPrEEE8XsrYiMsMLE2HhKNgRv8eVl8liveWe1+v15pXGVx1GEIziGKnhwAQ24hSa0gMAInuEV3hzhvDjvzse8teDkM4fwB87nD/pJjYI=</latexit>

O(|f ⇤ |)
<latexit sha1_base64="HbFVquxzF+/OJk3Li9zvOXvf27w=">AAAB73icbVBNT8JAEJ3iF+IX6tHLRmKCHkgLJuqNxIs3MZGPBCrZLlvYsN3W3a0JKfwJLx40xqt/x5v/xgV6UPAlk7y8N5OZeV7EmdK2/W1lVlbX1jeym7mt7Z3dvfz+QUOFsSS0TkIeypaHFeVM0LpmmtNWJCkOPE6b3vB66jefqFQsFPd6FFE3wH3BfEawNlLrtjj2H87Gp918wS7ZM6Bl4qSkAClq3fxXpxeSOKBCE46Vajt2pN0ES80Ip5NcJ1Y0wmSI+7RtqMABVW4yu3eCTozSQ34oTQmNZurviQQHSo0Cz3QGWA/UojcV//PasfYv3YSJKNZUkPkiP+ZIh2j6POoxSYnmI0MwkczcisgAS0y0iShnQnAWX14mjXLJqZTKd+eF6lUaRxaO4BiK4MAFVOEGalAHAhye4RXerEfrxXq3PuatGSudOYQ/sD5/AA3Cj0s=</latexit>

Time Complexity:
O(E|f ⇤ |)
<latexit sha1_base64="I9Bhs1qojKFO+ubGyqD6SnbVbQc=">AAAB8XicbVBNS8NAEJ3Ur1q/qh69LBaheihJFdRbQQRvVrAf2May2W7apZtN2N0IJe2/8OJBEa/+G2/+G7dtDtr6YODx3gwz87yIM6Vt+9vKLC2vrK5l13Mbm1vbO/ndvboKY0lojYQ8lE0PK8qZoDXNNKfNSFIceJw2vMHVxG88UalYKO71MKJugHuC+YxgbaSH2+I1GvmPJ6PjTr5gl+wp0CJxUlKAFNVO/qvdDUkcUKEJx0q1HDvSboKlZoTTca4dKxphMsA92jJU4IAqN5lePEZHRukiP5SmhEZT9fdEggOlhoFnOgOs+2rem4j/ea1Y+xduwkQUayrIbJEfc6RDNHkfdZmkRPOhIZhIZm5FpI8lJtqElDMhOPMvL5J6ueSclsp3Z4XKZRpHFg7gEIrgwDlU4AaqUAMCAp7hFd4sZb1Y79bHrDVjpTP78AfW5w/0TY/E</latexit>
O(E|f ⇤ |)
<latexit sha1_base64="I9Bhs1qojKFO+ubGyqD6SnbVbQc=">AAAB8XicbVBNS8NAEJ3Ur1q/qh69LBaheihJFdRbQQRvVrAf2May2W7apZtN2N0IJe2/8OJBEa/+G2/+G7dtDtr6YODx3gwz87yIM6Vt+9vKLC2vrK5l13Mbm1vbO/ndvboKY0lojYQ8lE0PK8qZoDXNNKfNSFIceJw2vMHVxG88UalYKO71MKJugHuC+YxgbaSH2+I1GvmPJ6PjTr5gl+wp0CJxUlKAFNVO/qvdDUkcUKEJx0q1HDvSboKlZoTTca4dKxphMsA92jJU4IAqN5lePEZHRukiP5SmhEZT9fdEggOlhoFnOgOs+2rem4j/ea1Y+xduwkQUayrIbJEfc6RDNHkfdZmkRPOhIZhIZm5FpI8lJtqElDMhOPMvL5J6ueSclsp3Z4XKZRpHFg7gEIrgwDlU4AaqUAMCAp7hFd4sZb1Y79bHrDVjpTP78AfW5w/0TY/E</latexit>

|f*|denotes a maximum flow in the network

26
Ford-Fulkerson Algorithm

• Why we come up with maximum flow when there is no augmentation

path in Gf ?

• Theorem (Max-flow min-cut theorem): The following are equivalent:

• f is a maximum flow
• Gf has no augmenting path

27
The Edmonds-Karp Algorithm

• We can improve the bound on Ford-Fulkerson by finding the

augmenting path p in line 3 with a breadth-first search

• That is, we choose the augmenting path as a shortest path from s to t

in the residual network, where each edge has unit distance (weight)

• The Edmonds-Karp algorithm runs in

30
Wrap-up

• We learned about flow networks

• Definitions
• Properties
• Max flow problem
• Ford-Fulkerson
• Edmonds-Karp

31