CSE 565
,
Lecture 10
. 09/27/2021
Network Flow
Pet 1Mtwork) : A tuple
– directed graph G- = IV , E)
– capacity cle) 70 , He c- E.
– sources c-V and sink 1- c-V.
1indegree of s=o) lout- degree oft =D .
Example :
11-1–7
+ ¥¥÷%%
Def ls-t_fw of a network) : f : E- → Rt . satisfying
i. 1 capacity constraint) : 0£ fly a- Cle) Feet
2. ( conservation constraint) :
Ie c-Ivy -114
= Ieeow, -114
. the c- Nss ,t}
IN = { lu.DE E} : in – edges of ✓
OH = { iv. w) c- E) : out- edges of a .
Def-lvalueofans-t-twt.lt/–Ieeocg-tK1 .
Fonti If / = Jeep till = Ie c-Iit, fll) –
Proof : Jeezy fly = Zeeow, fieV-uc-VIHBFEVYS.tl¥-1M t ‘ =¥vys,tj ⇐ 01b$
left ¥v Ieez,,,tH
–
Jeezy, th
–
Ee
c-1¥”
‘
= ⇐Etll) – o
– Ieezitfk
right = ¥, Igoµ,
tie – Eas,t'”
–
Eat,t'”
=
E-Efle)
– Ifl – 0
let = right
‘
⇒ Ifl = Ie eat, till ☒ .
Probtem Imax – flow )
Input : network G- = ME) . cle) 70 He c-E, sit c-V.
output : an s – t flow f- sit . If / is maximized .
5- { s , a. b}
c 15,1-7=10
.
*:;¥÷÷¥¥÷÷÷÷:* ..
CCS, -11=4 -1121-31-8=27
Det 1st cut of a network ) , partition of V
CS
, 1- = V15) , sit . SES . and TET .
Note µt¥ElS,T)={uw)EE / UES. 0£31
•→• ETTTS) ={ lu.DE/uc-T.vc-S}
” ”
Els
, 5) = { Lu, DEE/ u . V c- S}
E- ( T, T) = { luis EE/ UN ET } .
Det-ccapa-i-yofans-tcutj.cl
ST) = Iee Els , -1)
d ‘
Probtem 1min – cut ) .
Inpu a network G- = IV, El, el e)70 V-ec-E.si/-c-V .
output : an s- t cut 1¥ sit . els , -1) is minimized .
Claim: Let f- beaty s -t flow , and let 1ST) be
⇒
-t cut
, of the same network . Then
Ifl I cls, -1) .
using Isil
⑤'”→⑦ 11-1–7 |s-+os¥%% “Sitio
feel – -2Proof: HI = ¥0 ,, fie,
= -2
£ “” → 0
tie) .
EEE 1ST) e c-FITS)
a- Iee-tls.pe/e)-0–clS,T) ☒,
Max-flow
I
→É⇒ IR
1ft I 4s , -1)
min- cut .
Font : 1£ 11-1=45,1-1 , then f- is a max -flow
and 1ST) is a min – cut .
Question : Do they# meet ?
Ante : Yes !
proof: constructive proof .
Algorithmi-ord-T-ulksoni.find an s-t flow f- and an s-t cut 1ST)
sit . Ifl = Cls , -1) .
⇒ f- is a max-flow and Csi is a min – out .
⇒ max-flow = min – cut . on every network.
Idea:_ iterative improvement .