CSE 565 , lecture 12 . 10/06/2021
Note The pretlow – push algo always maintains a poeftwf
and taking h that are compatible
Fat:_ It flow is a special case of preflow .
Det : We say an edge in .us c- Gf is active , if
hlu) = hw , -11 .
Example
⑤¥¥¥÷÷¥§¥É¥¥±
2
Fanti let t be a pre flow . If there exists an s-t path
in Gf, then there does not exist any labeling h that is
compatible with f- .
Proofs 1 by contradiction )
P in G-f : §→o→→→o→
t .
his)=n hit =o
therefore : its aotpossink to satisfy the steepness condition
for all edges in p , as # ledges in P) = n – i .
Fanti Let f- be a pre flow . It there does not exist an s-t path
in Gf, then there always exist a labeling h that is
compatible with f.
proof : 1 constructive proof,
–
+
Gf :
S = { u c- V1 s can reach u}
1- = V15
⇒ + c-T . ⇒ IS , IT is an s
-t cat .
Det : hlu) = n , it v c-Shiv) =o , if u E T .
High-level idea of pp algorithm
– maintains f and h that are compatible
– wpdatesfandh 1 path & relabel)
– terminates when f becomesaftow .
Fonti Let f- be a flow . Then the followings are equivalent .
i. there does not exists s – t path in Gt
2. there exists a labeling that is compatible
with f.
3. f is a maximum flow .
Init :
¥¥¥¥÷*5¥. > 0
016)
Gt : ⑤←É-⑤
s¥÷°
fusion
Applies an edge a- lung in Gf .
Xflu)> 0
Applicable:×µu, > o . Ft:
2. e is active
,
e.g.,hiu-hlw-lproadurei-flec-fle-minfxflu.ge#
case / irxfiuyzq ,
saturating -Pash non- saturating push
case 2 : Xfl < Cfl
el
¥1
÷i±¥h .it#+?'" ¥h,it
'" '
4-19
U V 4-19 -Xtlu
✗flu)←Xflu1 -9-14 Xflu)←Xflul - Xfm
Xfw)←XfW -19-19 Xfw)←XfWtXf1u)
Exampte :
Gt :
0¥ old
(-147
* 16)
push Caa,
push " 't!
µ⑤←8¥>⑤%)É¥¥%,
a-+ :
*
Fa after push . f- is still apreflow.FI: f- and h are compatible afterpushug .
Rela.be# operation
Applies to a vertex
Applicable to u c- V1 { sit} , if :
1 . Xflu) > 0 .
2. all edges in Ola) are not active
I push can’t be applied)
procedure: hlu) ← him -11 .
Eixample :
Gt :
⑤
←É¥⑤”
5 019
1- 147
016)
① relabel (a)
Gt :
⑤
¥0s”
5T
c- 14
019
0161
Fatty: hand f- are still compatible -after relabeling .
Algorithm pretlow – push ( G-= 14Th . clekov-ec-E.s.tl .
init h and f.
while ( 7- u c- V1 { sit} sit . Xflu) >0 ) .
arbitrarily pick ns.t.xflu > 0 .
if l I laid C- Etf , Sit . lab is active )| pick arbitrarily such an edge my| push luivelse| yea, man , ,u,
end .
end .
Example :
610) 210)
¥
.
%