PowerPoint Presentation
Network Flow &
Linear Programming
Jeff Edmonds York University
COSC 3101
Lecture 5
Thinking about Algorithms Abstractly
Optimization Problems
Network Flow Defn
Simple Example
Application: Matching
Flow Strategy
Hill Climbing
Augmenting Flow
Primal-Dual Hill Climbing
Min Cut
Max Flow = Min Cut
Running Time
Linear Programming
‹#›
1
Ingredients:
Instances: The possible inputs to the problem.
Solutions for Instance: Each instance has an exponentially large set of solutions.
Cost of Solution: Each solution has an easy to compute cost or value.
Specification
Optimization Problems
‹#›
2
Instance:
A Network is a directed graph G
Edges represent pipes that carry flow
Each edge has a maximum capacity c
A source node s out of which flow leaves
A sink node t into which flow arrives
Goal:
Max Flow
Network Flow
‹#›
3
Instance:
A Network is a directed graph G
Edges represent pipes that carry flow
Each edge has a maximum capacity c
A source node s out of which flow leaves
A sink node t into which flow arrives
Network Flow
‹#›
4
Network Flow
For some edges/pipes,
it is not clear which direction the flow should go
in order to maximize the flow from s to t.
Hence we allow flow in both directions.
‹#›
5
Network Flow
u
v
1719
244
This edge/pipe allows
download at a rate of 1719kbps
OR upload at a rate of 244kbps
Not both
simultaneously
‹#›
6
Network Flow
u
v
75
10
This edge/pipe allows flow
to the right at a rate of 75 L/sec
OR to the left right at a rate of 10 L/sec
‹#›
7
Network Flow
u
v
15/75
0/10
This edge/pipe allows flow
to the right at a rate of 75 L/sec
OR to the left right at a rate of 10 L/sec
Currently the flow is
to the right at 15 L/sec
‹#›
8
Network Flow
u
v
0/75
5/10
This edge/pipe allows flow
to the right at a rate of 75 L/sec
OR to the left right at a rate of 10 L/sec
Currently the flow is
to the left at 5 L/sec
‹#›
9
Solution:
The amount of flow F through each edge.
Flow can’t exceed capacity i.e. F c.
Unidirectional flow
F 0 and F
or
F = 0 and F
Some texts:
F = -F
Network Flow
‹#›
10
Solution:
The amount of flow F through each edge.
Flow F can’t exceed capacity c.
Unidirectional flow
No leaks, no extra flow.
Network Flow
‹#›
11
Solution:
The amount of flow F through each edge.
Flow F can’t exceed capacity c.
Unidirectional flow
No leaks, no extra flow.
For each node v: flow in = flow out
u F = w F
Except for s and t.
Network Flow
‹#›
12
Value of Solution:
Flow from s into the network
minus flow from the network back into s.
rate(F) = u F
= flow from network into t
minus flow back in.
= u F – v F
– v F
What about
flow back into s?
Goal:
Max Flow
Network Flow
‹#›
13
A network
with its edge capacities
Network Flow
What is the maximum that can flow from s to t?
‹#›
14
A network
with its edge capacities
Network Flow
The max total rate of the flow is 1+2-0 = 3.
flow/capacity = 2/5
Prove that total can not be higher.
‹#›
15
No more flow can be pushed
along the top path because the
edge is at capacity.
Similarly, the edge
No flow is pushed along the bottom path because this would decrease the total from s to t.
Network Flow
‹#›
16
is a minimum cut
Its capacity is the sum of the capacities crossing the cut
= 1+2 = 3.
is not included in because it is going in the wrong direction.
Network Flow
‹#›
17
The edges crossing forward across the cut are at capacity
those crossing backwards have zero flow.
This is always true.
Network Flow
‹#›
18
The maximum flow is 1+2=3
The minimum cut is 1+2=3.
These are always equal.
Network Flow
‹#›
19
An Application: Matching
Sam Mary
Bob Beth
John Sue
Fred Ann
Who loves whom.
Who should be matched with whom
so as many as possible matched
and nobody matched twice?
3 matches
Can we do better?
4 matches
‹#›
20
An Application: Matching
s
t
c = 1
Total flow out of u = flow into u 1
Boy u matched to at most one girl.
1
c
Total flow into v = flow out of v 1
Girl v matched to at most one boy.
1
u
v
‹#›
21
Network Flow
Strategy:
Push flow into s.
Must make decisions.
Get stuck and must backtrack.
Difficult and time consuming.
s
c=100
f=100
c=100
c=100
c=1
f=100
‹#›
22
Network Flow
Strategy:
Find a path for a single drop.
Push as much flow through as fits.
w = augment = Min Path c
‹#›
23
Network Flow
Strategy:
Find a path for a single drop.
Push as much flow through as fits.
w = augment = Min Path c
flow/capacity = 20/21
‹#›
24
Network Flow
Given Flow F
Construct Augmenting Graph GF
Find path P using BFS, DFS,
or generic search algorithm
Let w be the max amount flow
can increase along path P.
Increase flow along path P by w.
i.e newF = oldF + w × P
+w
+w
+w
+w
‹#›
25
Network Flow
Given Flow F
Construct Augmenting Graph GF
Find path P using BFS, DFS,
or generic search algorithm
No path
Stop.
‹#›
26
Hill Climbing
We have a valid solution.
(not necessarily optimal)
Take a step that goes up.
measure
progress
Value of our solution.
Problems:
Exit
Can’t take a step that goes up.
Running time?
Initially have the “zero
Local Max
Global Max
Can our Network Flow
Algorithm get stuck
in a local maximum?
Make small local changes to your solution to
construct a slightly better solution.
If you take small step,
could be exponential time.
‹#›
27
Network Flow
Previous Input
Previous Output
Same Input
Can our Network Flow Algorithm
get stuck in local max?
Worse Output
Need only one example.
Yes!
‹#›
28
Network Flow
‹#›
29
Network Flow
Previous Input
Previous Output
Same Input
Yes! Our Network Flow
Algorithm can get stuck.
Worse Output
Need only one example.
‹#›
30
Hill Climbing
Avoiding getting stuck
in a local maximum
Good Execution
Bad Execution
Made better choices of direction
Hard
Back up an retry
Exponential time
Define a bigger step
‹#›
31
Hill Climbing
Different
Solutions
Current
Solution
Alg defines
to where alg can step
i.e. what small local
changes can be made to
current solution
This defines
the topography
‹#›
32
Hill Climbing
Different
Solutions
Current
Solution
Define a slightly
bigger step
This defines
the topography
Perhaps removes some local maxima
‹#›
33
Network Flow
Previous Input
Previous Output
Same Input
Worse Output
Mistake?
Putting 2 through
this edge
‹#›
34
Network Flow
Mistake?
Putting 2 through
this edge
We need to decrease the flow in this edge.
But if we decrease the total flow then
the algorithm might run exponentially
or forever.
We need to decrease the flow in this edge
AND increase the total flow.
‹#›
35
Network Flow
Let us focus on how much
we can CHANGE
the rate of flow
through a given edge.
‹#›
36
Network Flow
u
v
15/75
0/10
This edge/pipe allows flow
to the right at a rate of 75 L/sec
OR to the left right at a rate of 10 L/sec
Currently the flow is
to the right at 15 L/sec
‹#›
37
Network Flow
u
v
15/75
0/10
Currently the flow is
to the right at 15 L/sec
u
v
F[-10,75]
Eqv Flow Graph
F = 15
15
‹#›
38
u
v
0/75
10/10
Currently the flow is
to the left at 10 L/sec
u
v
F[-10,75]
Eqv Flow Graph
F = -10
15
Network Flow
‹#›
39
Network Flow
Add 5 flow to right
u
v
F[-10,75]
Eqv Flow Graph
F = 15
15
Current Flow
20
u
v
F[-10,75]
Eqv Flow Graph
F = 20
Resulting Flow
‹#›
40
Network Flow
Add -5 flow to right
u
v
F[-10,75]
Eqv Flow Graph
F = 15
15
Current Flow
10
u
v
F[-10,75]
Eqv Flow Graph
F = 10
Resulting Flow
Equivalent
Add 5 flow to left
‹#›
41
Network Flow
Add -20 flow to right
u
v
F[-10,75]
Eqv Flow Graph
F = 15
15
Current Flow
-5
u
v
F[-10,75]
Eqv Flow Graph
F = -5
Resulting Flow
Add 20 flow to left
Equivalent
‹#›
42
Network Flow
-5
u
v
F[-10,75]
Eqv Flow Graph
F = -5
Resulting Flow
u
v
-5/75
0/10
Flow Graph
u
v
0/75
5/10
Flow Graph
Equivalent
‹#›
43
Network Flow
15+Δ ≤ 75
F+Δ ≤ c
Δ ≤ c-F
Walking Δ
u
v
15+Δ /75
0/10
New Flow Graph
u
v
F[-10,75]
Eqv Flow Graph
F = 15
15
75-15 = 60
Allowed change
to the right
‹#›
44
Network Flow
15-Δ ≥ -10
F-Δ ≥ -c
Δ ≤ F + c
u
v
15- Δ /75
0/10
New Flow Graph
Walking Δ
u
v
F[-10,75]
Eqv Flow Graph
F = 15
Allowed Flow
≠
Allowed Change in Flow
15
Allowed change
to the left
15+10=25
‹#›
45
Network Flow
Δ ≤ F + c
u
v
F[-10,75]
Eqv Flow Graph
F = 15
Δ ≤ c-F
u
v
Augmentation Graph
15
75-15 = 60
Allowed change
to the right
Allowed change
to the left
15+10=25
‹#›
46
Network Flow
Given Flow F
Construct Augmenting Graph GF
Find path P
Old
New
Where we got stuck before
‹#›
47
Network Flow
Given Flow F
Construct Augmenting Graph GF
Find path P
Let w be the max amount flow
can increase along path P.
Increase flow along path P by w.
i.e newF = oldF + w × P
+w
+w
+w
-w
?
‹#›
48
Network Flow
Given Flow F
Construct Augmenting Graph GF
Find path P using BFS, DFS,
or generic search algorithm
No path
Stop.
‹#›
49
Network Flow
Previous Input
Previous Output
Same Input
Worse Output
Same Output
‹#›
50
‹#›
51
An Application: Matching
Sam Mary
Bob Beth
John Sue
Fred Ann
Who loves whom.
Who should be matched with whom
so as many as possible matched
and nobody matched twice?
3 matches
Can we do better?
4 matches
‹#›
52
An Application: Matching
s
t
Flow
s
t
Augmentation Graph
Augmentation Path
Alternates
adding edge
removing edge
adding edge
removing edge
adding edge
Extra edge added
s
t
New Flow
‹#›
53
An Application: Matching
Sam Mary
Bob Beth
John Sue
Fred Ann
Who loves whom.
Who should be matched with whom
so as many as possible matched
and nobody matched twice?
3 matches
Can we do better?
4 matches
‹#›
54
Network Flow
Can our Network Flow Algorithm
get stuck in local max?
Need to prove
for every input network
for every choice of augmenting paths
Maximum Flow is found!
No!
How?
‹#›
55
Primal-Dual Hill Climbing
Mars settlement has hilly landscape
and many layers of roofs.
‹#›
56
Primal-Dual Hill Climbing
Primal Problem:
Exponential # of locations to stand.
Find a highest one.
Dual problem:
Exponential # of roofs.
Find a lowest one.
‹#›
57
Primal-Dual Hill Climbing
Prove:
Every roof is above every location to stand.
R L height(R) height(L)
height(Rmin) height(Lmax)
Is there a gap?
‹#›
58
Primal-Dual Hill Climbing
Prove:
For every location to stand either:
the alg takes a step up or
the alg gives a reason that explains why not
by giving a roof of equal height.
i.e. L [ L’ height(L’) > height(L) or
R height(R) = height(L)]
or
But R L height(R) height(L)
No Gap
‹#›
59
Primal-Dual Hill Climbing
Prove:
For every location to stand either:
the alg takes a step up or
the alg gives a reason that explains why not
by giving a roof of equal height.
i.e. L [ L’ height(L’) > height(L) or
R height(R) = height(L)]
or
Can’t go up from this location
and no matching roof.
Can’t happen!
?
‹#›
60
Primal-Dual Hill Climbing
Prove:
For every location to stand either:
the alg takes a step up or
the alg gives a reason that explains why not
by giving a roof of equal height.
i.e. L [ L’ height(L’) > height(L) or
R height(R) = height(L)]
or
No local maximum!
‹#›
61
Primal-Dual Hill Climbing
Claim: Primal and dual have the same optimal value.
height(Rmin) = height(Lmax)
Proved: R L, height(R) height(L)
Proved: Alg runs until it provides Lalg and Ralg
height(Ralg) = height(Lalg)
No Gap
height(Rmin)
height(Ralg) =
height(Lalg)
height(Lmax)
height(Rmin)
height(Lmax)
Lalg witness that height(Lmax) is no smaller.
Ralg witness that height(Lmax) is no bigger.
Exit
‹#›
62
A network
with its edge capacities
Network Flow
What is the maximum that can flow from s to t?
‹#›
63
A network
with its edge capacities
Network Flow
The max total rate of the flow is 1+2-0 = 3.
flow/capacity = 2/5
Prove that total can not be higher.
‹#›
64
No more flow can be pushed
along the top path because the
edge is at capacity.
Similarly, the edge
No flow is pushed along the bottom path because this would decrease the total from s to t.
Network Flow
‹#›
65
is a minimum cut
Its capacity is the sum of the capacities crossing the cut
= 1+2 = 3.
is not included in because it is going in the wrong direction.
Network Flow
‹#›
66
The edges crossing forward across the cut are at capacity
those crossing backwards have zero flow.
This is always true.
Network Flow
‹#›
67
The maximum flow is 1+2=3
The minimum cut is 1+2=3.
These are always equal.
Network Flow
‹#›
68
Primal-Dual Network Flow
Primal Problem: Max Flow
Dual Problem:
Min Cut
What are the roofs to the flows?
‹#›
69
Instance:
A Network is a directed graph G
Special nodes s and t.
Edges represent pipes that carry flow
Each edge has a maximum capacity c
Min Cut
s
t
‹#›
70
Instance:
A Network is a directed graph G
Special nodes s and t.
Edges represent pipes that carry flow
Each edge has a maximum capacity c
Min Cut
‹#›
71
Solution:
C = partition of nodes with sU, tV.
Min Cut
s
t
U
V
York
UC Berkeley
= Canada
= USA
‹#›
72
Min Cut
s
t
York
UC Berkeley
Ontario
Solution:
C = partition of nodes with sU, tV.
‹#›
73
Min Cut
s
t
York
UC Berkeley
Toronto
Solution:
C = partition of nodes with sU, tV.
‹#›
74
Min Cut
s
t
York
UC Berkeley
York
Solution:
C = partition of nodes with sU, tV.
‹#›
75
Min Cut
s
t
York
UC Berkeley
UCB
Solution:
C = partition of nodes with sU, tV.
‹#›
76
Min Cut
s
t
York
UC Berkeley
Berkeley
Solution:
C = partition of nodes with sU, tV.
‹#›
77
Min Cut
s
t
York
UC Berkeley
U
V
Solution:
C = partition of nodes with sU, tV.
‹#›
78
Value Solution C=:
cap(C) = how much can flow from U to V
= uU,vV c
Min Cut
s
t
U
V
u
v
Goal:
Min Cut
‹#›
79
Theorem:
For all Networks MaxF rate(F) = MinC cap(C)
Prove: F,C rate(F) cap(C)
Max Flow = Min Cut
U
V
u
v
Prove: flow F, alg either
finds a better flow F
or finds cut C such that rate(F) = cap(C)
Alg stops with an F and C for which rate(F) = cap(C)
F witnesses that the optimal flow can’t be less
C witnesses that it can’t be more.
Exit
‹#›
80
cap(C) = how much can flow from U to V
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV F – F
Lemma: rate(F) = rate(F,C) cap(C)
Max Flow = Min Cut
Prove: flow F, cut C rate(F) cap(C)
s
t
U
V
York
UC Berkeley
= Canada
= USA
+
–
F c & F
No leaks, no extra flow.
‹#›
81
Lemma: F,C rate(F,C) = rate(F)
Proof: By induction on the size of U.
Base case: C = <{s},G-{s}>
rate(F) = Flow from s into the network
minus flow from the network back into s
= u F – v F
= rate(F,C) where C = <{s},G-{s}>
Max Flow = Min Cut
s
t
York
UC Berkeley
+
–
‹#›
82
Lemma: F,C rate(F,C) = rate(F)
Proof: By induction on the size of C.
Base case: C = <{s},G-{s}>
Inductive step: Move nodes across C one at a time.
Max Flow = Min Cut
Flow into x = Flow out.
Hence, flow across cut does not change.
rate(F) = rate(F,C) cap(C)
‹#›
83
Theorem:
For all Networks MaxF rate(F) = MinC cap(C)
Prove: F,C rate(F) cap(C)
Max Flow = Min Cut
U
V
u
v
Prove: flow F, alg either
finds a better flow F
or finds cut C such that rate(F) = cap(C)
‹#›
84
Given Flow F
Construct Augmenting Graph GF
Find path P
Let w be the max amount flow
can increase along path P.
Increase flow along path P by w.
i.e newF = oldF + w × P
+w
+w
+w
-w
Max Flow = Min Cut
‹#›
85
Given Flow F
Construct Augmenting Graph GF
Find path P using BFS, DFS,
or generic search algorithm
No path
Stop
Max Flow = Min Cut
‹#›
86
Let Falg be this final flow.
Let cut Calg=,
where U are the nodes reachable from s
in the augmented graph
and V not.
Claim: rate(Falg) = cap(Calg)
Max Flow = Min Cut
Bad example because
U might contain
more than s.
‹#›
87
Max Flow = Min Cut
Prove: rate(Falg) = cap(Calg)
Prove: rate(Falg,Calg) = cap(Calg)
=
‹#›
88
cap(C) = how much can flow from U to V
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV F – F
Max Flow = Min Cut
Prove: rate(Falg,Calg) = cap(Calg)
+
F/c
u
v
F/c
Flow Graph
U
V
v’
u’
–
‹#›
89
Max Flow = Min Cut
F/c
u
v
F/c
Flow Graph
U
V
v’
u’
need equal
need zero
+
–
cap(C) = how much can flow from U to V
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV F – F
Prove: rate(Falg,Calg) = cap(Calg)
‹#›
90
Max Flow = Min Cut
u
v
F/c
Flow Graph
c-F
F+c
U
V
v’
u’
F/c
u
Augmentation Graph
U
V
v’
v
u’
reachable from s =
= not
not edges
=0
=0
need equal
+
need zero
–
cap(C) = how much can flow from U to V
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV F – F
Prove: rate(Falg,Calg) = cap(Calg)
‹#›
91
Theorem:
For all Networks MaxF rate(F) = MinC cap(C)
Prove: F,C rate(F) cap(C)
Max Flow = Min Cut
U
V
u
v
Prove: flow F, alg either
finds a better flow F
or finds cut C such that rate(F) = cap(C)
Alg stops with an F and C for which rate(F) = cap(C)
F witnesses that the optimal flow can’t be less
C witnesses that it can’t be more.
‹#›
92
Hill Climbing
Problems:
Can our Network Flow
Algorithm get stuck
in a local maximum?
Local Max
Global Max
No!
‹#›
93
Hill Climbing
Problems:
Running time?
If you take small step,
could be exponential time.
‹#›
94
Network Flow
‹#›
95
Network Flow
Add flow 1
‹#›
96
Network Flow
Add flow 1
‹#›
97
Hill Climbing
Problems:
Running time?
If each iteration you take
the biggest step possible,
Alg is poly time
in number of nodes
and number of bits in capacities.
If each iteration you take
path with the fewest edges
Alg is poly time
in number of nodes
‹#›
98
Taking the biggest step possible
‹#›
m = # edges
l = # bits to specify capacities.
The flow Ft must increase from 0 to up to
To be poly time, we could have Ft double each iteration.
But it does not
Taking the biggest step possible
F0 = 0
FT = m2l
m2l
T = log(m) + l
Rt = How much the flow can increase by
= MaxFlow – Ft
To be poly time, we could have Rt half each iteration.
Or decrease by a (1-1/m) factor
Taking the biggest step possible
R0 = m2l
= 0
RT = 0
Rt = How much the flow can increase by
= MaxFlow – Ft
Choose any cut C = U,V.
Rt ≤ eC augmente
Taking the biggest step possible
s
t
U
V
u
v
Let wt = amount Ft increases
= the min augment in augmenting path
Let Cut = U,V
where nodes uU are reachable from s
with edges with augment amount > wt,
i.e. the last graph in previous algorithm
for which s is not reachable from t.
eC augmente ≤ eC wt ≤ m wt
(where m = # edges in graph)
Taking the biggest step possible
s
t
U
V
u
v
Rt = MaxFlow – Ft
≤ eC augmente
Taking the biggest step possible
≤ m wt ≤ m amount Ft increases
≤ m amount Rt decreases
Rt+1 = Rt – amount Rt decreases
≤ Rt – 1/m Rt
= (1– 1/m) Rt
Decreasing by an mth!
Does this stop after m iterations?
No because as decreases,
the decrease decreases.
Rt = How much the flow can increase by
= MaxFlow – Ft
To be poly time, we could have Rt
decrease by a (1-1/m) factor each iteration
Taking the biggest step possible
R0 = m2l
= 0
RT = 0
Rt+1 ≤ (1– 1/m) Rt
End game: 1/2, 1/4, 1/8, 1/16, …. ?
All flows are integers.
Hence, decreasing RT < 1 is good enough.
Taking the biggest step possible
Rt+1 ≤ (1– 1/m) Rt
RT ≤
< 1
(1– 1/m)T R0
Taking the biggest step possible
< 1
(1– 1/m)T R0
(e-1/m)T R0
Taking the biggest step possible
< 1
(1– 1/m)T R0
(e-1/m)T R0
(e-T/m) R0
-T/m + ln(R0) = ln(1) = 0
T = m ln(R0)
= m ln(m2l)
= m (l + ln m)
m = # edges
l = # bits to specify capacities.
Linear Programming
‹#›
109
A Hotdog
A combination of pork, grain, and sawdust, …
‹#›
110
Constraints:
Amount of moisture
Amount of protein,
…
‹#›
111
The Hotdog Problem
Given today’s prices,
what is a fast algorithm
to find the cheapest hotdog?
‹#›
112
Abstract Out Essential Details
Cost: 29, 8, 1, 2
Amount to add: x1, x2, x3, x4
pork
grain
water
sawdust
3x1 + 4x2 – 7x3 + 8x4 ≤ 12
2x1 - 8x2 + 4x3 - 3x4 ≤ 24
-8x1 + 2x2 – 3x3 - 9x4 ≤ 8
x1 + 2x2 + 9x3 - 3x4 ≤ 31
Constraints:
moisture
protein,
…
29x1 + 8x2 + 1x3 + 2x4
Cost of Hotdog:
‹#›
113
29x1 + 8x2 + 1x3 + 2x4
Subject to:
Minimize:
Abstract Out Essential Details
3x1 + 4x2 – 7x3 + 8x4 ≤ 12
2x1 - 8x2 + 4x3 - 3x4 ≤ 24
-8x1 + 2x2 – 3x3 - 9x4 ≤ 8
x1 + 2x2 + 9x3 - 3x4 ≤ 31
‹#›
114
A Fast Algorithm
For decades people thought that there was no fast algorithm.
Then one was found!
Theoretical Computer Science
finds new algorithms every day.
3x1 + 4x2 – 7x3 + 8x4 ³ 12
2x1 - 8x2 + 4x3 - 3x4 ³ 24
-8x1 + 2x2 – 3x3 - 9x4 ³ 8
x1 + 2x2 + 9x3 - 3x4 ³ 31
29x1 + 8x2 + 1x3 + 2x4
Subject to:
Minimize:
»
‹#›
115
Network Flow as a
Linear Program
Given an instance of Network Flow:
express it as a Linear Program:
The variables:
Maximize:
Subject to:
Flows f for each edge.
: F c. (Flow can’t exceed capacity)
v: u F = w F
rate(F) = u F – v F
‹#›
116
‹#›
117
Primal
Dual
‹#›
118
End
‹#›
119
Network Flow
Locally in each edge,
we see how much we can change the flow.
Allowed Flow ≠ Allowed Change in Flow
People find this hard.
This is my first attempt to explain it.
‹#›
120
Network Flow
u
v
0/75
0/10
Old Flow Graph
Walking 10
u
v
10/75
0/10
New Flow Graph
‹#›
121
Network Flow
u
v
0/75
0/10
Old Flow Graph
Walking 10
u
v
0/75
10/10
New Flow Graph
‹#›
122
Network Flow
u
v
0/75
0/10
Old Flow Graph
Walking -10
u
v
-10/75
0/10
New Flow Graph
Same
Walking 10
u
v
0/75
10/10
New Flow Graph
Not allowed
‹#›
123
Network Flow
Walking -10
u
v
-10/75
0/10
New Flow Graph
Same
Walking 10
u
v
0/75
10/10
New Flow Graph
Not allowed
u
v
F[-10,75]
Eqv Flow Graph
F = -10
‹#›
124
Network Flow
10+Δ ≤ 75
F+Δ ≤ c
Δ ≤ c-F
Walking Δ
u
v
10+Δ /75
0/10
New Flow Graph
u
v
F[-10,75]
Eqv Flow Graph
F = 10
‹#›
125
Network Flow
10-Δ ≥ -10
F-Δ ≥ -c
Δ ≤ F + c
u
v
10- Δ /75
0/10
New Flow Graph
Walking Δ
u
v
F[-10,75]
Eqv Flow Graph
F = 10
‹#›
126
Network Flow
Δ ≤ F + c
u
v
F[-10,75]
Eqv Flow Graph
F = 10
Δ ≤ c-F
u
v
Augmentation Graph
‹#›
127
Network Flow
Locally in each edge,
we see how much we can change the flow.
Allowed Flow ≠ Allowed Change in Flow
People find this hard.
This is my second attempt to explain it.
‹#›
128
Network Flow
u
v
0/75
0/10
Flow Graph
u
v
75
10
Augmentation Graph
‹#›
129
Network Flow
75-21=54
u
v
21/75
0/10
Flow Graph
u
v
Augmentation Graph
2
21+2=23
Walking
‹#›
130
Network Flow
75-21=54
u
v
21/75
0/10
Flow Graph
u
v
Augmentation Graph
10
21-10=11
10
Edge shouldn’t
have flow in
both directions.
0
10
?
Walking 10
Walking -10
‹#›
131
Network Flow
75-21=54
u
v
11/75
0/10
Flow Graph
u
v
Augmentation Graph
10
10
?
Capacity of 10 not met
‹#›
132
Network Flow
75-21=54
u
v
21/75
0/10
Flow Graph
u
v
Augmentation Graph
21
10
?
Capacity of 10 exceeded
21
‹#›
133
Network Flow
75-21=54
u
v
21/75
0/10
Flow Graph
u
v
Augmentation Graph
21
21-21=0
10
?
Capacity of 10 not met
Walking 21
Walking -21
‹#›
134
Network Flow
75-21=54
u
v
21/75
0/10
Flow Graph
u
v
Augmentation Graph
21+10
21-21=0
10
10
?
21+10=31
Capacity of 10 met
Walking 21
and another 10
‹#›
135
Network Flow
75-21=54
21+10=31
u
v
21/75
0/10
Flow Graph
u
v
Augmentation Graph
25
21-25=-4
4
0
Walking 25
‹#›
136
u
v
F/c
0/c
Flow Graph
u
v
Augmentation Graph
F+w
w
Walking
c-F
F+c
c
F
c
Network Flow
‹#›
137
u
v
F/c
0/c
Flow Graph
u
v
Augmentation Graph
F-w
c-F
F+c
c
F
c
w
Walking
Network Flow
‹#›
138
‹#›
Network Flow
How much flow
can I have
in each direction?
u
v
0/75
0/10
Where can I stand
in each direction?
‹#›
140
Network Flow
How much flow
can I have
in each direction?
75 to the right
u
v
75/75
0/10
Where can I stand
in each direction?
‹#›
141
Network Flow
How much flow
can I have
in each direction?
75 to the right
u
v
0/75
10/10
10 to the left
Where can I stand
in each direction?
‹#›
142
Network Flow
u
v
15/75
0/10
Add 5 flow to right
Walking 5
u
v
20/75
0/10
15
20
‹#›
143
Network Flow
u
v
15/75
0/10
Add 75-15=60
flow to right
Walking 75-15=60
u
v
75/75
0/10
15
‹#›
144
Network Flow
u
v
15/75
0/10
How much flow can
I add to right
How much can I change
my position to the right?
75-15=60
15
u
v
75-15=60
Augmentation Graph
‹#›
145
Network Flow
u
v
f/c
0/10
How much flow can
I add to right
How much can I change
my position to the right?
75-15=60
15
f-c
u
v
Augmentation Graph
‹#›
146
Network Flow
u
v
15/75
0/10
Add 5 flow to left
Walking 5
u
v
15/75
5/10
Edge shouldn’t
have flow in
both directions.
15
10
‹#›
147
Network Flow
u
v
15/75
0/10
Add 5 flow to left
Walking 5
u
v
15-5=10/75
0/10
15
10
‹#›
148
Network Flow
u
v
15/75
0/10
Add 15 flow to left
Walking 15
u
v
15-15=0/75
0/10
15
‹#›
149
Network Flow
u
v
15/75
0/10
Add 15+5=20
flow to left
Walking 15+5=20
u
v
-5/75
0/10
Edge shouldn’t
have negative flow.
15
-5
‹#›
150
Network Flow
u
v
15/75
0/10
Add 15+5=20
flow to left
Walking 15+5=20
u
v
0/75
5/10
15
-5
‹#›
151
Network Flow
u
v
15/75
0/10
Add 15+10=25
flow to left
Walking 15+10=25
u
v
0/75
10/10
15
‹#›
152
Network Flow
u
v
15/75
0/10
How much flow can
I add to left
How much can I change
my position to the left?
15+10=25
15
15
u
v
15+10=25
Augmentation Graph
‹#›
153
Network Flow
u
v
f/75
0/c
How much flow can
I add to left
How much can I change
my position to the left?
15+10=25
15
15
u
v
f+c
Augmentation Graph
‹#›
154
u
v
F/c
0/c
Flow Graph
u
v
Augmentation Graph
F+w
w
Walking
c-F
F+c
c
F
c
Network Flow
‹#›
155
u
v
F/c
0/c
Flow Graph
u
v
Augmentation Graph
F-w
c-F
F+c
c
F
c
w
Walking
Network Flow
‹#›
156
/docProps/thumbnail.jpeg