Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
5. FLOW NETWORKS
office: K17 202
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem
3. Applications of Network Flow
4. Puzzle
Flow Networks
Definition
A flow network G = (V ,E ) is a directed graph in which each edge
e = (u, v) ∈ E has a positive integer capacity c(u, v) > 0.
There are two distinguished vertices: a source s and a sink t; no
edge leaves the sink and no edge enters the source.
s
v1
v2
v3
v4
t
16
12
20
13
14
4
10 4
9
7
Flow Networks
Examples of flow networks (possibly with several sources and many
sinks):
transportation networks
gas pipelines
computer networks
and many more.
Flow Networks
Definition
A flow in G is a function f : E → [0,∞), f (u, v) ≥ 0, which
satisfies
1. Capacity constraint: for all edges e(u, v) ∈ E we require
f (u, v) ≤ c(u, v),
i.e. the flow through any edge does not exceed its capacity.
2. Flow conservation: for all vertices v ∈ V − {s, t} we require∑
(u,v)∈E
f (u, v) =
∑
(v ,w)∈E
f (v ,w),
i.e. the flow into any vertex (other than the source and the
sink) equals the flow out of that vertex.
Flow Networks
Definition
The value of a flow is defined as
|f | =
∑
v :(s,v)∈E
f (s, v) =
∑
v :(v ,t)∈E
f (v , t),
i.e. the flow leaving the source, or equivalently, the flow arriving at
the sink.
Given a flow network, our goal is to find a flow of maximum value.
Maximum Flow
Integrality Theorem
If all capacities are integers (as we assumed earlier), then there is a
flow of maximum value such that f (u, v) is an integer for each
edge (u, v) ∈ E .
Note
This means that there is always at least one solution entirely in
integers. We will only consider integer solutions hereafter.
Maximum Flow
In the following example, f /c represents f units of flow sent
through an edge of capacity c .
s
v1
v2
v3
v4
t
11/16
12/12
15/20
8/13
11/14
4/4
0/10 1/4
4/9
7/7
The pictured flow has a value of 19 units, and it does not appear
possible to send another unit of flow. But we can do better!
Maximum Flow
Here is a flow of value 23 units in the same flow network.
s
v1
v2
v3
v4
t
11/16
12/12
19/20
12/13
11/14
4/4
0/10 1/4
0/9
7/7
Maximum Flow
This example demonstrates that the most basic greedy
algorithm - send flow one unit at a time along arbitrarily
chosen paths - does not always achieve the maximum flow.
What went wrong in the first attempt?
We sent 19 units of flow to vertex v3, only to send four units
back to v2.
It would have been better to send those four units of flow to t
directly, but this may not have been obvious at the time this
decision was made.
We need a way to correct mistakes! We would like to send
flow from v2 back to v3 so as to “cancel out” the earlier
allocation.
Residual Flow Network
Definition
Given a flow in a flow network, the residual flow network is the
network made up of the leftover capacities.
Flow network Residual flow network
s
v1
v2
v3
v4
t
11/16
12/12
15/20
8/13
11/14
4/4
0/10 1/4
4/9
7/7 s
v1
v2
v3
v4
t
5
11
12
5
15
5
8
3
11
4
11 3
4
5
7
Residual Flow Network
Suppose the original flow network has an edge from v to w
with capacity c , and that f units of flow are being sent
through this edge.
The residual flow network has two edges:
1. an edge from v to w with capacity c − f , and
2. an edge from w to v with capacity f .
These capacities represent the amount of additional flow in
each direction. Note that sending flow on the “virtual” edge
from w to v counteracts the already assigned flow from v to
w .
Edges of capacity zero (when f = 0 or f = c) need not be
included.
Residual Flow Network
Suppose the original flow network has an edge from v to w
with capacity c1 and flow f1 units, and an edge from w to v
with capacity c2 and flow f2 units.
What are the corresponding edges in the residual graph?
How much flow can be sent from v to w (and vice versa)?
The forward edge allows c1 − f1 additional units of flow, and
we can also send up to f2 units to cancel the flow through the
reverse edge.
Thus we create edges from v to w with capacity c1 − f1 + f2
and similarly from w to v with capacity c2 − f2 + f1.
Augmenting Paths
Definition
An augmenting path is a path from s to t in the residual flow
network.
The residual flow network below corresponds to the earlier example
of a flow of value 19 units. An augmenting path is pictured in red.