[SOLVED] CS代写 Algorithms & Data Structures (Winter 2022) Graphs – Flow Network 1

Algorithms & Data Structures (Winter 2022) Graphs – Flow Network 1

Announcements

Copyright By PowCoder代写加微信 assignmentchef

• 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) 0,therearef(e)unitsof
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 Efwith 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/3Flow networkFlow Residual graphs s forward s backward 0/1 0/1 0/1 1/1 1 10/1 0/1 1/1 0/1 1 1 tttResidual graphs – Example 2/3Flow networkFlow s 2/2Residual graph forward s backward2/3 t 0/1 3-2=1 t 1 24Residual graphs – Example 3/3Residual graphs – Example 3/3Residual graphAugmenting pathAn 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 – ExampleResidual s graph GfAugmenting path – ExampleResidual graph Gf Augmented path in Gf s (value of the flow isthe bottleneck value)2 2 2 29 9 9 / 3Augmenting path – Example 3/3 Gs 3/4 t 3/3 0/3 2/2Gf s 2/3 t 0/10/3 2/3 2/2Methodology• Compute the residual graph Gf• FindapathP• Augment the flow f along the path P1. Letβbethebottleneck(smallestresidualcapacity cf(e) of edges on P)2. Addβtotheflowf(e)oneachedgeofP. Q: How do we add β into G?Augmenting a pathf.augment(P) {β = min { cf(e) | e ∈ P }foreach edgee=(u,v)∈P{ if e is a forward edge {} else { // e is a backward edgef(e) -= β }Ford-Fulkerson algorithmFord-Fulkerson algorithmFord-Fulkerson algorithmFord-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代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]