程序代写代做代考 algorithm PowerPoint Presentation

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 : The input is one instance. : A valid solution with optimal cost. (minimum or maximum)
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 = 0
or
F = 0 and F  0

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

‹#›
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

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

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

But  R  L height(R)  height(L)

No Gap

‹#›
59

Primal-Dual Hill Climbing

Can’t go up from this location
and no matching roof.
Can’t happen!
?

‹#›
60

Primal-Dual Hill Climbing

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

‹#›
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 sU, tV.

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 sU, tV.

‹#›
73

Min Cut
s
t

York

UC Berkeley

Toronto
Solution:
C = partition of nodes with sU, tV.

‹#›
74

Min Cut
s
t

York

UC Berkeley

York
Solution:
C = partition of nodes with sU, tV.

‹#›
75

Min Cut
s
t

York

UC Berkeley

UCB
Solution:
C = partition of nodes with sU, tV.

‹#›
76

Min Cut
s
t

York

UC Berkeley

Berkeley
Solution:
C = partition of nodes with sU, tV.

‹#›
77

Min Cut
s
t

York

UC Berkeley

U
V
Solution:
C = partition of nodes with sU, tV.

‹#›
78

Value Solution C=:
cap(C) = how much can flow from U to V
= uU,vV 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
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV 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  0
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
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV 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
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV 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’

u’
reachable from s =
= not
not edges
=0
=0
need equal

+
need zero

–

cap(C) = how much can flow from U to V
= uU,vV c
rate(F,C) = Flow from U to V minus flow V to U
= uU,vV 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

‹#›
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 = m2l
m2l
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 = m2l
= 0
RT = 0

Rt = How much the flow can increase by
= MaxFlow – Ft
Choose any cut C = U,V.
Rt ≤ eC 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 uU 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.
eC augmente ≤ eC wt ≤ m wt
(where m = # edges in graph)
Taking the biggest step possible

s
t

U
V

u
v

Rt = MaxFlow – Ft
≤ eC 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 = m2l
= 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(m2l) = 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 (flow in = flow out)
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

21+2=23
Walking

‹#›
130

Network Flow
75-21=54

u
v
21/75
0/10
Flow Graph

u
v
Augmentation Graph

21-10=11

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

‹#›
133

Network Flow
75-21=54

u
v
21/75
0/10
Flow Graph

u
v
Augmentation Graph

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

21-25=-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

‹#›
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

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

‹#›
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

‹#›
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

Related Posts