程序代写代做代考 algorithm Network Flow

Network Flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 559 / 606

Network Flow Problem
18 v5 14
v2
26 12 25
16
s35v4 t
v7
26
28 15
32 30 22
v1
v6
source
19 v3 25
flow
sink
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 560 / 606

Network Flow Problem
18 v5 14
v2
15 16
s35v4 t
v7
26 15 12 25
32
26
1028 15214 6 30
v1 4 4 v6 19 v3 25
flow
22
source
sink
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 561 / 606

Setting up the Problem
Let G = (V,E) be a directed graph
Edge flow:
Flow is associated with each edge in E Amount of flow over edge e ∈ E written as f (e)
Edge capacity:
Each edge e ∈ E as a flow capacity c(e) Flow for edge cannot exceed this capacity
f(e) ≤ c(e) for all e ∈ E We will assume that c(e) is an integer
David Weir (U of Sussex) Program Analysis Term 1, 2015 562 / 606

Setting up the Problem
Edges in and out of a node:
out(v) = {e | e = (v,u) for some u ∈ V } in(v) = {e | e = (u,v) for some u ∈ V }
Sink and source
Goal is to maximise flow from the source to the sink No edges into source, i.e.: in(s) = {}
No edges out of sink, i.e.: out(t) = {}
Conservation of flow:
For each node v, total flow into v equals total flow out of v
􏰃 f(e) = 􏰃 f(e) e ∈ in(v) e ∈ out(v)
David Weir (U of Sussex) Program Analysis
Term 1, 2015
563 / 606

Setting up the Problem
Flow of a network:
Flow is conserved at each node in the network
Therefore the flow out of the source equals the flow into the sink This is the flow of the network
v(f) = 􏰃 f(e) e ∈ out(s)
We want to maximise v(f)
= 􏰃 f(e) e ∈ in(t)
David Weir (U of Sussex) Program Analysis
Term 1, 2015 564 / 606

Simple Example
100
v3
50
70
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
565 / 606

Simple Example
100
v3
50
70
100
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
566 / 606

Simple Example
v3
100
100
40
50
70
60
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
567 / 606

Simple Example
v3
100
100
40
50
70
60
40
s v2 t 45
50
100 25
v1
David Weir (U of Sussex) Program Analysis
Term 1, 2015
568 / 606

Simple Example
v3
100
100
40
50
70
60
40
s v2 t 45
100
50
v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
569 / 606

Simple Example
v3
100
100
40
50
70
60
40
s v2 t 45
100
5 50 v1
25
30
25
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
570 / 606

Simple Example
v3
100
100
40
50
70
60
45
s v2 t 45
100
5 50 v1
25
30
25
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
571 / 606

Untapped Capacity
Looking for improved flow:
Total flow achieved is 130
Network can support a flow of 140
Push 10 more units of flow along the path (s, v1, v2, v3, t) Redirecting 10 units of flow from (v3, v2) to (v3, t)
Potential for redirection of flow captured in the residual graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 572 / 606

Residual Graphs
100/100
v3
40/50
60/70
s v2 t 45/45
30/100
70
5/50
v1
25/25
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
573 / 606

Residual Graphs
v3
100/100
10
60/70
10
40/50
s v2 t 45/45
30/100
70
45
5/50
25/25
v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
574 / 606

Residual Graphs
100
v3
60 10
10
40
s v2 t 45
70
45 5
v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
575 / 606

Residual Graphs
100
v3
60 10
10
40
s v2 t 45
70
45 5
v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
576 / 606

Residual Graphs
Residual Graphs:
Given some directed graph G = (V,E) and some flow f for G The residual graph of G and f will be denoted by Gf
Forward and backwards edges:
Forward edges show additional flow capacity of edge — solid lines
Backward edges show capacity to re-direct flow — dashed lines
— reverse direction of edge original graph
Residual capacity: capacity of an edge in the residual graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 577 / 606

Residual Graph Definition
Suppose we have the following:
A graph G = (V,E) with edge capacities given by c Aflowf forG
Residual graph Gf is defined as follows:
V is the set of vertices in Gf ife=(u,v)isinE andf(e) 0 then
include edge (v,u) in Gf with capacity f(e) (v,u) is marked as a backward edge
David Weir (U of Sussex) Program Analysis Term 1, 2015 578 / 606

Bottleneck Edges
Flow in residual graph:
Path from s to t represents route for augmenting the flow
Capacity of path determined by the path’s bottleneck edge
A path’s bottleneck edge is edge with lowest capacity
Flow of network can be augmented by capacity of bottleneck edge
David Weir (U of Sussex) Program Analysis Term 1, 2015 579 / 606

Augmenting Flow
100
v3
60
10
10
40
s v2 t 45
70
45 5 v1
25
30
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
580 / 606

Augmenting Flow
A possible augmentation:
We have identified a path from s to t in the residual graph
— path is (s,v1,v2,v3,t)
The bottleneck edge of this graph has residual capacity 10 We can add 10 units of additional flow to this network
Augmenting a flow using a path:
Increment flow of each forward edge on path by 10
— corresponds to adding new flow along an under-capacity edge
Decrement flow of edges in G that give rise to backward edge on path by 10
— corresponds to redirecting existing flow elsewhere
David Weir (U of Sussex) Program Analysis Term 1, 2015 581 / 606

Flow Augmentation General Case
Suppose we have each of the following:
A graph G = (V,E) with source s and sink t
A flow f on G and corresponding residual graph Gf
A simple path p in Gf from s to t with bottleneck edge having residual capacity x
augment(G, f , p, x ) is defined as:
for each edge (u, v) in the path p if (u, v) is a forward edge then
f(u,v) ← f(u,v) + x
if (u, v) is a backward edge then
f(v,u) ← f(v,u) − x return f
David Weir (U of Sussex) Program Analysis Term 1, 2015 582 / 606

Augmented Flow in Example
v3
100
100
40-10
50
70
60+10
45
s v2 t 45
30+10
100
25
5+10
50
25
v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
583 / 606

Augmented Flow in Example
v3
100
100
30
50
70
70
45
s v2 t 45
100
25
40
25
15
50
v1
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
584 / 606

Ford-Fulkerson Algorithm
MaximumFlow(G, s, t, c, ):
let f(e) = 0 for all e ∈ E
let Gf be the residual graph built from G and f whilethereisapathfromstot inGf
letpbeasimplepathfromstot inGf
let x be the residual capacity of the bottleneck edge of p f ← augment(G,f,p,x)
let Gf be the residual graph built from G and f
return f
David Weir (U of Sussex) Program Analysis Term 1, 2015 585 / 606

Implementing Ford-Fulkerson
Finding a s to t path in the residual graph:
Perform depth-first search from s
Takes O(n + m) time
O(m), since we assume all vertices have at least one incident edge
Iterations of while loop?
Flow is increases by at least one on every iteration — assumes edge capacities are integers
Flow is a measure of progress
Number of iterations bounded by upper bound on flow, C Overall running time is O(Cm)
David Weir (U of Sussex) Program Analysis Term 1, 2015 586 / 606

Upper bound on Network Flow
Upper bounds on flow through a network
Can’t exceed what the source can produce
v(f) ≤ 􏰃 c(e) e ∈ out(s)
Can’t exceed what the sink can accept
v(f) ≤ 􏰃 c(e) e ∈ in(t)
There is something more general that can be said
David Weir (U of Sussex) Program Analysis Term 1, 2015 587 / 606

Cuts in a Network
Let G = (V,E) be some network
(A, B) is a cut of the network if: s is in A
t is in B
A∪B=V andA∩B={}
In other words (A, B) is a partition of the set V
David Weir (U of Sussex) Program Analysis Term 1, 2015 588 / 606

Example Cut
20 60
s 80 t 30
David Weir (U of Sussex) Program Analysis Term 1, 2015 589 / 606

Cut Capacity
Let G = (V,E) be a network and (A,B) be a cut of G
The capacity of the cut (A, B), denoted c(A, B) is as follows:
c(A,B) = 􏰃 c(u,v)
(u,v) ∈ E u∈A v∈B
Cut capacity and network flow:
Many different possible cuts
The maximum flow is equal to minimum cut capacity
Captures what might be described as the network’s bottleneck
David Weir (U of Sussex) Program Analysis Term 1, 2015 590 / 606

Example Cut
20 60
s 80 t 30
Capacity of this cut is 20+80+30 = 130
David Weir (U of Sussex) Program Analysis Term 1, 2015 591 / 606

Correctness of Algorithm
The following propositions can be established:
Every cut provides an upper bound on the maximum possible flow The algorithm finds a flow that equals the capacity a particular cut The algorithm finds the maximum flow of the network
The algorithm finds the least capacity of any cut of the network
See textbook for details of the proofs
David Weir (U of Sussex) Program Analysis Term 1, 2015 592 / 606

Network Flow: Bipartite Matching
David Weir (U of Sussex) Program Analysis Term 1, 2015 593 / 606

Bipartite Graphs
A graph G = (V,E) is a bipartite graph if:
V can be partitioned into two sets V1 and V2
V = V1 ∪ V2 and V1 ∩ V2 = {} we can say that (V1, V2) is a partition of V
Everyedgee∈E hasoneendinV1 andoneendinV2
David Weir (U of Sussex) Program Analysis Term 1, 2015 594 / 606

Matching of Bipartite Graphs
M is a matching of a bipartite graph G = (V,E) if: M is a set of edges from E
M⊆E
Each vertex appears in at most one edge in M
if {u,v} ∈ M then there is no v′ ̸= v such that {u,v′} ∈ M
David Weir (U of Sussex) Program Analysis Term 1, 2015 595 / 606

Bipartite Matching Problem
Given a bipartite graph G = (V , E ) the bipartite matching problem is the problem of finding the largest possible matching M for G.
We will assume that the partition (V1, V2) is given
David Weir (U of Sussex) Program Analysis Term 1, 2015 596 / 606

Bipartite Matching Example
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
597 / 606

Bipartite Matching as Network Flow
Suppose G = (V,E) is a bipartite graph with partition (V1,V2) Construct weighted, directed G′ = (V′,E′) from G as follows:
Include two nodes additional nodes in G′ V′ =V∪{s,t}
Each edge in E placed in E′, directed edge from V1 to V2 Extra edges from s to each node in V1
Extra edges from each node in V2 to t
Every edge in E′ given capacity of 1
David Weir (U of Sussex) Program Analysis Term 1, 2015 598 / 606

Bipartite Matching as Network Flow
x1
x2 sx3 x4 x5
y1
y2 y3t y4
y5
David Weir (U of Sussex)
Program Analysis
Term 1, 2015 599 / 606

Maximum Flow is Largest Matching
Size of largest matching of G is equal to maximum flow of G′ Edges with non-zero flow make up the largest match
To justify this we make several observations
David Weir (U of Sussex) Program Analysis Term 1, 2015 600 / 606

All Matches are Flows
Observation: If M is a match then there is a flow k = |M|
Let all edges in match have flow of 1
Let edges from s to vertices involved in edges have flow of 1 Let edges to t from vertices involved in edges have flow of 1 By properties of matchings all flow is conserved
Total flow is |M|
David Weir (U of Sussex) Program Analysis Term 1, 2015 601 / 606

Integer Flows
Observation: Only need to consider flows that are integers
Given all edge capacities are integer
Ford-Fulkerson algorithm produces flows that are integers Ford-Fulkerson finds maximum flow
When edge capacities are all integers so is the maximum flow
Observation: Flow on each edge is either 0 or 1
David Weir (U of Sussex) Program Analysis Term 1, 2015 602 / 606

Matching Property
Observation: Only one edge in matching for any member of V1
Suppose v is in V1
Flow into v is at most 1
Flowoutofv isatmost1
Only one edge out v has non-zero flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 603 / 606

Matching Property
Observation: Only one edge in matching for any member of V2
Suppose v is in V2
Flowoutofv isatmost1
Flow into v is at most 1
Only one edge into v has non-zero flow
David Weir (U of Sussex) Program Analysis Term 1, 2015 604 / 606

Maximum Flows are Matches
Observation: If there is a maximum flow k then there is a matching M with |M| = k
Suppose there is a maximum flow of k
Can assume all flows are integers
Every path from s to t includes exactly one edge from V1 to V2 k edges from V1 to V2 must have flow of 1
Let M be all such edges
From last 2 observations M is a matching
Size of matching M is k
David Weir (U of Sussex) Program Analysis Term 1, 2015 605 / 606

Running Time
The Ford-Fulkerson algorithm takes O(Cm) time C is upper bound on flow (source’s output) m is number of edges in network
In case of bipartite matching:
Upper bound on flow is the number of nodes n So running time is O(nm)
David Weir (U of Sussex) Program Analysis Term 1, 2015 606 / 606