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

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

Announcements

Copyright By Assignmentchef 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) I 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) I 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 Naive algorithm
Initialize f = 0
While true {
if( pathPfromstotsuchthatall edges have a flow less than capacity)
increase flow on P up to max

Maximum-Flow Naive 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. Letbethebottleneck(smallestresidualcapacity cf(e) of edges on P)2. Addtotheflowf(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)eE 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]