Flow and Matching
Flow and Matching
Flow digraph:D(V,E) source:s sink:t capacity:c:E→R+ 0/1 0/1 0/1 0/1 0/3 S 0/3 0/4 0/1 0/4 0/1
Flow digraph: D(V,E) capacity: c : E R+ 0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3 s t source: s sink: t
Flow digraph:D(V,E) source:s sink:t capacity:c:E→R+ flow:f:E→R 1/1 1/3 S 1/3 1/1 214 capacity:∀(u,w)∈E,fuv≤cuw conservation:u∈V\{s,t},∑(u,wEBfwu=∑u,)EBfw
Flow 1/1 2/4 0/1 1/1 1/1 1/1 1/1 2/4 1/3 1/3 digraph: D(V,E) capacity: c : E R+ source: s sink: t s t flow: f : E R+ ⇤(u, v) ⇥ E, fuv cuv ⇥u V \{s, t}, (w,u)E fwu = (u,v)E fuv capacity: conservation:
14 1/1 1/3 1/3 2 1/1 214 0/T capacity::(u,w)∈E,fuu≤cuu conservation:u∈V\{s,t,∑(u,)E fwu=∑(u,)EEfuv value of ∑∑fsu=∑ft flow: (s,u)∈E (w,t)∈E maximum flow
1/1 2/4 0/1 1/1 1/1 1/1 1/1 2/4 1/3 1/3 s t ⇤(u, v) ⇥ E, fuv cuv ⇥u V \{s, t}, (w,u)E fwu = (u,v)E fuv capacity: conservation: (s,u)E fsu = (v,t)E fvt value of flow: maximum flow
0/1 1/1 1/1 2/3 23 1/1 314 0/T capacity:(u,v)∈E,fuw≤cuu conservation::u∈V八{s,t,∑(u,)EBSwu=∑(u,w)EBfw value of ∑∑fsu=∑ft flow: (s,u)∈E (w,t)∈E maximum flow
1/1 3/4 0/1 1/1 1/1 0/1 1/1 3/4 2/3 2/3 s t ⇤(u, v) ⇥ E, fuv cuv ⇥u V \{s, t}, (w,u)E fwu = (u,v)E fuv capacity: conservation: (s,u)E fsu = (v,t)E fvt value of flow: maximum flow
Maximum Flow digraph:D(V,E) source:s sink:t capacity:c:E→&+ max ∑f u:(s,u)∈E s.t.0≤fuv≤Cu ∀(u,v)∈E ∑fww-∑fu=0 u∈V\{s,t} w:(w,u)∈E w:(u,v)∈E integral flow:fuu∈Z (u,v)∈E
Maximum Flow digraph: D(V,E) capacity: source: s sink: t max u:(s,u)E fsu ⇥(u, v) E ⇥u V \ {s, t} w:(w,u)E fwu v:(u,v)E fuv = 0 s.t. 0 fuv cuv c : E R+ Z+ integral flow: fuv Z ⇥(u, v) E
Cut digraph:D(V,E) source:s sink:t capacity:c:E→R+ 0/1 0/1 0/1 0/1 0/3 0/3 0/4 0/1 0/1 s-t cut; SCV Cuv s∈S,ttS u∈S,vtS,(u,w)∈E
Cut digraph: D(V,E) capacity: c : E R+ 0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3 s t source: s sink: t uS,v⇥S,(u,v)E s-t cut: cuv s S, t ⇥ S S V
Cut digraph:D(V,E) source:s sink:t capacity:c:E→R+ 0/1 0/1 0/3 0/3 0/4 minimum cut 0/1 s-t cut: SCV Cuv s∈S,ttS u∈S,vtS,(u,w)∈E
0/1 0/4 0/1 0/1 0/1 0/1 0/1 0/4 0/3 0/3 s t Cut digraph: D(V,E) capacity: c : E R+ source: s sink: t uS,v⇥S,(u,v)E s-t cut: cuv s S, t ⇥ S S V minimum cut
Fundamental Facts of Max-Flow Integrality causes no additional difficulties. ●max-flow=min-cut
• Integrality causes no additional difficulties. • max-flow = min-cut Fundamental Facts of Max-Flow
Augmenting Path 1/1 1/1 1/1 1/1 1/3 S 1/3 214 1/1 2/4 0/1 augmenting path:s uou1...uk =t f(uiui1)0 if Ui ui+l
Augmenting Path 1/1 2/4 0/1 1/1 1/1 1/1 1/1 2/4 1/3 1/3 s t augmenting path: s = u0u1 ··· uk = t f(uiui+1) 0 ui ui+1 ui ui+1 if if