程序代写代做代考 C algorithm graph Flows in Networks

Flows in Networks
Based on slides by David Kauchak
26 – Notes
Textbook 13
–
Chapter

Student networking
You decide to create your own campus network:
• Yougetthreeofyourfriendsandstringsomenetworkcables
• Becauseofcapacity(duetocabletype,distance,computer,etc) you can only send a certain amount of data to each person
• Ifedgesdenotecapacity,whatisthemaximumthroughputyoucan you send from S to T?
20
10
A 30
S
10
T B
20

Student networking
• You decide to create your own campus network:
• Yougetthreeofyourfriendsandstringsomenetworkcables
• Becauseofcapacity(duetocabletype,distance,computer,etc) you can only send a certain amount of data to each person
• Ifedgesdenotecapacity,whatisthemaximumthroughputyoucan you send from S to T?
20/20
S 10/10
A 10/30
10/10
T B
30 units
20/20

A flow problem
A4C
10
2
10 6
T 10
8
S
10
B9D
How much water flow can we continually send from s to t?

A flow problem
A4/4 C 6/8
B 4/9 D
14 units
10/10
2
4/10 6
T 10/10
S
4/10

Flow graph/networks
Flow network
• directed, weighted graph (V, E)
• positive edge weights indicating the “capacity”
• We assume that capacities are integers ( otherwise
• We assume that there are no edges (u,v) and (v,u)
FULKERSON
• contains a single source s 􏳔 V with no incoming edges
• contains a single sink/target t 􏳔 V with no outgoing edges
• everyvertexisonapathfromstot
A
10
30
10
B
20
S
T 20
the FORD –
scheme maynot halt

Flow
What are the constraints on flow in a network?
A
10
30
10
B
20
S
T 20

Flow
CONSTRAINTS
in-flow = out-flow for every vertex (except s, t)
flow along an edge cannot exceed the edge capacity flows are positive
A
10
30
10
B
20
S
T 20

Max flow problem
Given a flow network: what is the maximum flow we can send from s to t that meet the flow constraints?
Formally:aflowf isanassignmentofnumberstoedgessothatforall𝑒∈𝐸,𝑣∈𝑉 −{𝑠,𝑡} 0≤𝑓 𝑒 ≤𝑐 𝑒 ; //flowonedgeeisbelowcapacityofe
flow entering v = flow leaving v
|f| (total flow) = flow leaving s = flow entering t
We want to find a flow with maximal total flow.
A
20/20
S 10/10
• •
capacity
10/30
10/10
T B
20/20
BLUE is flow
BLACK is
CTOTAL) FLOW : 30 units

Applications?
network flow
• water, electricity, sewage, cellular… • traffic/transportation capacity
bipartite matching (matching organs to patients)
sports elimination (what team is eliminated for winning the championship at a given moment)
…

Max flow origins
Rail networks of the Soviet Union in the 1950’s
The US wanted to know how quickly the Soviet Union could get supplies through its rail network to its satellite states in Eastern Europe.
In addition, the US wanted to know which rails it could destroy most easily to cut off the satellite states from the rest of the Soviet Union.
These two problems are closely related, and that solving the max flow problem also solves the min cut problem of figuring out the cheapest way to cut off the Soviet Union from its satellites.
Source: lbackstrom, The Importance of Algorithms, at www.topcoder.com

Algorithm ideas?
graph algorithm?
• BFS, DFS, shortest paths… • MST
divide and conquer? greedy?
dynamic programming?
A
10
30
10
B
20
S
T 20

Algorithm idea
20
A
10
30
S
10
B
T 20

Algorithm idea
send some flow down a path
5
→
7
→9→5 : zo
20/20 S
10
A
10
20/30
20/20
T B

Algorithm idea
send some flow down a path
20/20 –
S
A
10
20/30 –
10/10
B
T 20/20
Now what?

Algorithm idea
reroute some of the flow
A
10/10
20/20
201
S
10/10
10/30
20/20
T B
Total flow?

Algorithm idea
reroute some of the flow
20/20 S
10/10
A
10/10
10/30
20/20
T B
30

Algorithm idea
A4C
10 6
T 10
S
10
B9D
10
2
8

Algorithm idea
send some flow down a path
A4C
9→7→9→5:8 10
8/10
2
8/8
6
8/10
S
10
T
B9D

Algorithm idea
sendsomeflowdownapath
5 → 7→ 2 → 5 : 2 T
8/10
10/10 S
10
A2/4 C 8/8
2 B9D
2/10 6

Algorithm idea
send some flow down a path
5→5→5→5:2 2/10
10/10 S
2/10
A2/4 C 8/8
2
B 2/9 D
6
10/10
T

Algorithm idea
5→ 9→ 7- 2→5iz 4/10
6
10/10
3→ A4/4 C
reroute some of the flow
10/10 S
4/10
6/8 2
B 4/9 D
T

Algorithm idea
A4/4 C 6/8
2
B 4/9 D
Are we done?
Is this the best we can do?
10/10 S
4/10
4/10 6
T 10/10

Cuts
A cut is a partitioning of the vertices into two sets L and R = V-L
A1CE
34245 4
BDF 46

Flow across cuts
In flow graphs, we’re interested in cuts that separate s from t, that is s 􏳔 L and t 􏳔 R
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
B 4/9 D

” 6
The flow “across” a cut is the total flow from nodes in L to nodes in R minus the total from from R to L
so
4/10
T
10/10
”
Flow across cuts
10/10 S
4/10
A4/4 C 6/8
2 6 B 4/9 D
10+10-6 14
=
What is the flow across this cut?
¥← 4 3
5

Flow across cuts
The flow “across” a cut is the total flow from nodes in L to nodes in R minus the total from from R to L
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
10+10-6 = 14
B 4/9 D

Flow across cuts
Consider any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitions the source from the sink
What do we know about the flow across the any such cut?
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
B 4/9 D

Flow across cuts
Consider any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitions the source from the sink
The flow across ANY such cut is the same and is the current total flow in the network
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
B 4/9 D

Flow across cuts
Consider any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitions the source from the sink
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
4+10 = 14
B 4/9 D

Flow across cuts
Consider any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitions the source from the sink
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
4+6+4 = 14
B 4/9 D

Flow across cuts
Consider any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitions the source from the sink
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
10+10-6 = 14
B 4/9 D

Flow across cuts
Consider any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitions the source from the sink
The flow across ANY such cut is the same and is the current flow in the network
Why? Can you prove it?
10/10 S
4/10
A4/4 C 6/8
2
4/10 6
T 10/10
B 4/9 D

Flow across cuts
The flow across ANY such cut is the same and is the current flow in the network
Inductively?
􏳕 everyvertexisonapathfromstot
• in-flow = out-flow for every vertex (except s, t)
• flow along an edge cannot exceed the edge capacity • flows are positive

Flow across cuts
The flow across ANY such cut is the same and is the c#urrent flow in the network
Base case: L = s
– Obvious: flow out of s = total flow
” so
*

Flow across cuts
The flow across ANY such cut is the same and is the current flow in the network
Inductive case: Consider moving a node x from R to L
Is the flow across the different partitions the same?
x

Flow across cuts
The flow across ANY such cut is the same and is the current flow in the network
Inductive case: Consider moving a node x from R to L
We look at the contribution of x in the crossing flow before and after the
move. Nothing else changes. flow = left-inflow(x) – left-outflow(x)
flow = right-outflow(x) – right-inflow(x)
x
left-inflow(x) + right-inflow(x) = left-outflow(x) + right-outflow(x) in-flow = out-flow left-inflow(x) – left-outflow(x) = right-outflow(x) – right-inflow(x)

tf. Capacity of a cut
The “capacity of a cut” is the maximum flow that we could send from nodes in L to nodes in R (i.e. across the cut)
How do we calculate the capacity?
A4C
–
:O so
-*
10
2
8
10 6
T 10
S
10
B9D

Capacity of a cut
Capacity of a cut is the sum of the capacities of edges crossing from L to R
A4C
10
2
8
10 6
T 10
S
10
B9D

Max flow Min Cut Theorem
Theorem: max flow = min (L,R) cut capacity(L,R) 5 Capacity is the sum of the edges from L to R
total flow We’ll see that we can have a flow |f*| = capacity of some cut (L,R)
So
min (L,R) cut capacity(L,R) ≥ max flow ≥ |f*| = capacity of some cut (L,R) ≥ min (L,R) cut capacity(L,R)
So: max flow = min cut capacity
Clearly any flow f
min (L,R) cut capacity(L,R)
.
14
.
μ€**
-*s
4
to
cannot be 2

Quick recap
A cut is a partitioning of the vertices into two sets L and R = V-L
For any cut where s 􏳔 L and t 􏳔 R, i.e. the cut partitionsthesourcefromthesink to totalflow
• the flow across any such cut is tahme¥sa#moe equal
• the maximum capacity (i.e. flow) across the cut is the
¥-##=#=⇒ sum of the capacities for edges from L to R
.FI#.ITFTeaEEaT.Ticapaatyouuewr
5
5
.
no fear,
>
= 4+2-3=3 6+3=9*31-3
4h -13-2*1
.
Current flow
i

Maximum flow
For any cut where s 􏳔 L and t 􏳔 R
• the flow across the cut is the same
• the maximum capacity (i.e. flow) across the cut is the sum of the capacities for edges from L to R
A4/4 C 6/8
2
B 4/9 D
Are we done?
Is this the best we can do?
10/10 S
4/10
4/10 6
T 10/10

Maximum flow
For any cut where s 􏳔 L and t 􏳔 R
• the flow across the cut is the same
• the maximum capacity (i.e. flow) across the cut is the sum of the capacities for edges from L to R
10/10 S
A4/4 C 6/8
2
4/10 6
T 10/10
B 4/9 D
4/10
We can do no better than the minimum capacity cut!

Maximum flow
What is the minimum capacity cut for this graph?
10/10 S
4/10
Capacity = 10 + 4
A4/4 C 6/8
2
4/10 6
B 4/9 D
Is this the best we can do?
T 10/10

Maximum flow
What is the minimum capacity cut for this graph?
10/10 S
Capacity = 10 + 4
A4/4 C 6/8
2
4/10 6
T 10/10
B 4/9 D
4/10
flow = minimum capacity, so we can do no better

The residual graph
For a flow f, we construct the residual graph Gf 𝐺􏳖 has the same nodes as G
Cvn)
and G.u) in Gg
↳ ” dummy edge”
Theedgesof𝐺􏳖: for each NN ) edge in G , w e put
For each edge e in the original graph (G): • if flow(e) < capacity(e) • introduce an edge in Gf with capacity = capacity(e)-flow(e) • this represents the remaining flow we can still push • if flow(e) > 0
• introduce an edge in Gf in the opposite direction with capacity = flow(e)
• this represents the flow that we can reroute/reverse

G: Ford-Fulkerson method or the augmented path algorithm
Ford-Fulkerson(G, s, t)
flow 𝑓􏳗= 0 for all edges e repeated vertices
[Gf = residualGraph(G)
while a simple path p exists from s to t in Gf (called an augmenting path) find the bottleneck value b on this path (min capacity of edges on the path)
f = update (f, p, b )
Gf = residualGraph(G) return flow f
-•
4
update (f,p, b){
for each edge e in the augmented path p
ifeedgeinG,f(e)=f(e) +b
if e is the reverse of e’ in G, f(e’) = f(e’)-b }
a simple path contains no
5
::S
→
…
so
.
o →:
←
: *: : c : : ÷ : : : : ÷ .

•
Initial flow
fe=o, forall e 20
EXAMPLE #Alg#or#ith#m #ide*a
I
A
build the .
residual g.am
Of 1 0
B
f.
Gf
T ol 20
910 G S 0130
01
20 S
10
A
10
30
T
.
•
Find a path from s to t in Gf
B
or-20 on all edgesin the path.
20
b=20
update flowby

Chihuahua
Algorithm idea
20/20 S
10
1.
A
10
G
20/30
20/20
S 20 Gf 10
B
T
.
Find a path from s to t in Gf
b= 10or- on all edgesin the path.
20
A
10
10
T B
20
• increase
flora by
10

Algorithm idea
G
T B
Hunicut
.
20
A
10
20
S 10 Gf 10
B
T
. Find a path from s to t in Gf
• NONEEASTS,So*e’reDONE.
20/20 S
A
10/10
10/10
10/30
20/20
20

EXAMPLE
Algorithm idea
2
WE#Att####u
G
10
B|
Gf
A4C
10 6
S
10
8 2
T 10
Find path5two5
B9D A4C
S
10
.
•
b=8 T
10
2
10
86 B9D
update by 10

mrnas
Algorithm idea
A4C
8/8 2
↳
G
8/10
S
10
f 2
8 S
10
10 6
G
A
4 C
8 2
fea.ba
be
B9D
T 8/10
• Find a path from
s to t in Gf
10 •update T
2
B9D
6
8

Algorithm idea
W hite-throated
G
10/10
S ↳ 10
A2/4 C 8/8
2/10 6
T 8/10
2 B9D
• Find a path from G A 2 C stotinGf
f
2 8
• updatefeoaobyb-_ 2
10 S
10
6
2
T
8 2
2 8
B9D

w in g m a n
Algorithm idea
A2/4 C 8/8
2
S
↳ 2/10
G
10/10
2/10 6
G
A
2 C 2
8
f
,
S
8
10 2
2 B7D
6
10
B 2/9 D
T 10/10
Find a path from stotinGf μ ,
• up,ay, , y, y
8 2
2
T
•

Algorithm idea
mummification
G A4/4 C
4/10 6
T 10/10
4/10
G A 4 C stotinGf
10/10 S
6/8 2
VI
B 4/9 D
f 6
S
6
2 B5D
T
10 2 4
664 10
4
•NONE EXISTS, So we’re DONE.
. Find a path from

sift:
• Every iteration increases the flow from s to t with bottleneck value b .
• Flow cannot be larger than the capacity of the min-cut = c*.
• So the loop can have at most c* iterations
• This argument does not work if edge capacities are not integers (and there are examples of such graphs where the algorithm does not terminate).
Ford-Fulkerson: is it correct?
Does the function terminate?

Whenitterminatesis |f|=themaximumflow?YES.
PROOF :
f = flow at the end
L = set of nodes reachable from s in residual 𝐺􏳖, R=V–L
t ∈ R because t is not reachable from s
If e= (u,v) is an edge crossing from L to R, f(e) = c(e ).
Otherwise v would be reachable from s.
If e =(v,u) is an edge crossing from R to L, f(e ) = 0. Otherwise v would be reachable from s.
So f = capacity (L,R). No flow can be larger, so f = max flow.
–
μR O
Final
=
so it ,
capacity at
=
this
is
O
flow
of
the wax flow

Ford-Fulkerson: runtime?
Ford-Fulkerson(G, s, t)
flow = 0 for all edges €
iteration :
– traverse the graph
– at most add 2 edges
while a simple path exists from s to t in Gf
send as much flow along path as possible – → 01mm
one
Gf = residualGraph(G)
for original edge
)
O(V +7E1) HI
Gf = residualGraph(G)
return flow
Can we simplify this expression?

Ford-Fulkerson: runtime?
iteration
– traverse the graph
– at most add 2 edges
for original edge
Ford-Fulkerson(G, s, t)
flow = 0 for all edges ✓
one
Gf = residualGraph(G)
while a simple path exists from s to t in GZ f
send as much flow along path as possible –
Gf = residualGraph(G)
return flow
O (1V1 +1 E, ) = O (1E 1) = 0 1 ‘ m – (all nodes exists on
paths exist from s to t)
is. man- ,
)
i
–

Ford-Fulkerson: runtime?
Ford-Fulkerson(G, s, t)
flow = 0 for all edges
Gf = residualGraph(G)
while a simple path exists from s to t in Gf
send as much flow along path as possible
Gf = residualGraph(G) return flow
– BFS or DFS
– O(1V1 +1E1) = O(1E1),
01M ) .

O(max-flow * E)
It
Can you construct a graph that could get this running time?
A
100
100 S
1 100
T 100
B

O(max-flow * E)
Can you construct a graph that could get this running time?
I
1
pale : 5→4→5→5
1/100 S
A
100
augmenting
1/1 100
T 1/100
B

O(max-flow * E)
Can you construct a graph that could get this running time?
1/100 A 1/100 augmenting
pale :
S 0/1 T 5→3→7→5
1/100
B
1/100

O(max-flow * E)
Can you construct a graph that could get this running time?
A
B
pale :
S 1/1 T 5→4→5→5
2/100
1/100
1/100 augmenting
2/100

O(max-flow * E)
Can you construct a graph that could get this running time?
2/100 A 2/100 augmenting
pale :
S 0/1 T 5→3→7→5
2/100
B
2/100

O(max-flow * E)
Can you construct a graph that could get this running time?
3/100 S
2/100
A
2/100
augmenting pale : 5→4→5→5
1/1
3/100
T B

O(max-flow * E)
Can you construct a graph that could get this running time?
A
3/100 augmenting pale :
5→7→7→5
3/100 S
3/100
What is the problem here? Could we do better?
0/1
3/100
T B

Faster variants
Edmunds-Karp
• Select the shortest path (in number of edges) from s to t in
Gf
• Howcanwedothis? • use BFS for search
• Running time: O(V E2) 1111
,
s o
Oln
–
m2 )
.
• avoidsissuesliketheonewejustsaw
• seethebookfortheproof
• or http://www.cs.cornell.edu/courses/CS4820/2011sp/handouts/ed mondskarp.pdf
preflow-push (aka push-relabel) algorithms
• O(IVll3)

Other variations…
http://en.wikipedia.org/wiki/Maximum_flow
http://akira.ruc.dk/~keld/teaching/algoritmedesign_f 03/Artikler/08/Goldberg88.pdf

↳
=s

CLAIM
CLAIM
So :
K. F-LOW = THAX MATCHING
Hatching of MAX
size
K ⇒ Flow of size
→
size

G= •,
Graphs — summary
–
(V E) IVI- n IEl= M
.
• adjacency matrix : O (NY space
• •
adjacency list : O (new ) space . TR AYERSALS
– BFSIS);.usesaqueue;
Visits a ll modes reachable from 5
– DFS CS) ; o uses a stack (or recursion)
• •
•
—→4 ( assuming each edge has cost = L )
,
determines shortest path 5 → OfMtm )
a ll nodes reachable from 5 if G is directed , DRS xx . timing
G
• visits .
•
about the structure of
forward , back, cross edge O(Mtm)
gives
info

TOPOLOGICAL SORTING
–
–
–
for DAG s ifpath6→ .
– –
→4teen4isbefore4 ,
O lntm)
.

•
mustbe >0
Ohmrlogn ) → t a n HEAP implementation
SHORTEST PATH
: shortest path from 5 to all 4
• •
Of n3 ) . IDEA :
,
SOURCE
SINGLE
DIJKSTRA : all weights
O knew ) . login ) =
.
O (n’+ m ) • IDEA :
array implementation . K is the set of ” known” vertices
→
Weight shortest 3 → . – – → 4 . using
•
and update its neighbors.
• BELLMAN- forb i weightscanbeco; nonegativecycle
d Ev]
ateach round, addtok thenodexx. smallestDED
O(n-m)
•: IDEA
( if G has negative cycle, Deffinds it ).
.–→4 having at most k edges, K = Oil, . . . in- l
.
=
a s ” stepping stoves nodes
ink
”
d Ev] – weight shortest 5 →
shortest path from any 2 to
ALL PAIRS :
• FLOYD- keArsHALL weightscauseco ; nonegativecycle
any 4
dEiJ]= weightofshortest1→. –→2
.
””4 …
using as stepping stones 410,2, , 4 K=0,I,n.. ,U.
.

•
ANIN SPANNING TREE
.
weights smallest weight connecting all
G = H e E ) undirected , connected , positive
FIND a tree in .
the KRUSKAL
•
IDEA
:
at
each
iteration ,
‘
IDEA : same as DIJKSTRA ,
but
K to4
nodes
al g
7
– O(mlogu)
add the smallest edge treat does not make a cycle .
ppl rn ‘or
Alg .
O Cme logu)✓ pain HEAP ofnzw.gr>ARRA’s
d Ev]
= shortest dist from
,

MAX FLOW
9 G= EYE) , each edgehasa capacity>O
, integer .
000
⇐
Florae
:
OE fee)E Cle)
.
conservation rule
–
EDMONDS- KARP- O(n-ni) .
FIND Max flow from 5 too 7
.
keep
satisfies
.
ta AX FLOW = TAIN CUT
–
– FORD – FULKERSON method
finding a n augmenting path 5→ – – 4
in residual Gf as long as we can
.
five I
path edges
shortest
augmenting fewest
BIPARTITE MATCHING
–
Algorithm by reduction to the MAX FLOW problem.
–
,

Related Posts