南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Flow and Matching

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 ￾ u￾S,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 ￾ u￾S,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