Algorithms & Data Structures (Winter 2022) Graphs – Flow Network 1
Announcements
Copyright By PowCoder代写 加微信 powcoder
• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2.
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.
Flow Network
G = (V, E) directed.
Each edge (u, v) has a capacity c(u, v) ≥ 0.
If (u,v) Ï E, then c(u,v) = 0.
Source vertex s, sink vertex t, assume s v
c(u,v) is a non-negative integer. If (u,v) ⍷ E, then (v,u) Ï E.
No incoming edges in source. No outcoming edges in sink.
t for all v ∈ V.
Flow Network – Definitions
Positive flow: A function p : V × V → R satisfying: Capacity constraint: For all u, v ∈ V, 0 ≤ p(u, v) ≤ c(u, v)
Flow conservation: For all u ∈ V − {s, t}, ∑p(v,u)= ∑p(u,v)
Positive flow
0/2 2/2 2/3
Flow into u
Flow in: 0 + 2 + 1 = 3 Flow out: 2 + 1 = 3
Flow out of u
Flow Network – Example
• Flow in == Flow out
• Source s has outgoing flow
• Sink t has ingoing flow
• Flow out of source s == Flow in the sink t
The value of the
flow: the total flow out of the source minus the flow into the source
|f|is also equal to the total net flow into the target vertex t
Maximum-Flow Problem
Given G, s, t, and c, find a flow whose value is maximum.
Maximum-Flow Problem – Applications
Maximum-Flow – Naïve algorithm
Initialize f = 0
While true {
if(∃ pathPfromstotsuchthatall edges have a flow less than capacity)
increase flow on P up to max
Maximum-Flow – Naïve algorithm
Initialize f = 0
While true {
if(∃ apathPfromstot s.t.all edgese ∈ Pf(e)
flow that we can “undo” if we want to, by pushing flow backward.
• The edges in Ef are either edges in E or their reversals.
Maximum-Flow – Residual graphs
for each edge e = (u, v) ∈ E if f(e) < c(e)
put a forward edge (u,v) in Ef
with residual capacity cf(e)=c(e)–f(e)
put a backward edge (v,u) in Ef with residual capacity cf(e) = f(e)
Residual graphs – Example 1/3
Flow network
Flow Residual graph
s s forward s backward 0/1 0/1 0/1 1/1 1 1
0/1 0/1 1/1 0/1 1 1 ttt
Residual graphs – Example 2/3
Flow network
Flow s 2/2
Residual graph forward s backward
2/3 t 0/1 3-2=1 t 1 24
Residual graphs – Example 3/3
Residual graphs – Example 3/3
Residual graph
Augmenting path
An augmenting path is a path from the source s to the sink t in the residual graph Gf that allows us to increase the flow.
Q: By how much can we increase the flow using this path?
Augmenting path - Example
Residual s graph Gf
Augmenting path - Example
Residual graph Gf
Augmented path in Gf s (value of the flow is
the bottleneck value)
2 2 2 29 9 9 / 3
Augmenting path - Example
3/3 Gs 3/4 t
3/3 0/3 2/2
Gf s 2/3 t 0/1
0/3 2/3 2/2
Methodology
• Compute the residual graph Gf
• FindapathP
• Augment the flow f along the path P
1. Letβbethebottleneck(smallestresidualcapacity cf(e) of edges on P)
2. Addβtotheflowf(e)oneachedgeofP. Q: How do we add β into G?
Augmenting a path
f.augment(P) {
β = min { cf(e) | e ∈ P }
foreach edgee=(u,v)∈P{ if e is a forward edge {
} else { // e is a backward edge
f(e) -= β }
Ford-Fulkerson algorithm
Ford-Fulkerson algorithm
Ford-Fulkerson algorithm
Ford-Fulkerson algorithm - complexity
• Let C= ∑c(e)
e∈E outgoing
• Finding an augmenting path from s to t takes O(|E|) (e.g. BFS or DFS).
• The flow increases by at least 1 at each iteration of the main while loop.
• The algorithm runs in O(C ∙ |E|)
• Introduction.
• Topological Sort. / Strong Connected Components
• Network Flow 1. • Introduction
• Ford-Fulkerson
• Network Flow 2.
• Shortest Path.
• Minimum Spanning Trees. • Bipartite Graphs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com