® marquage de c à partir de s : la capacité de (s, c) est 4 et f (s, c) = 0, donc
p c = min{∞, 4 − 0} = 4 et c reçoit la marque (s
+ , 4) ;
® marquage de a à partir de c : la capacité de (c, a) est 5, f (c, a) = 0, donc
p a = min{p c , 5 − 0} = 4 et a reçoit la marque (c
+ , 4) ;
® marquage de b à partir de a : p b = min{p a , c(a, b) − f (a, b)} = 4, donc b reçoit
la marque (a
+ , 4) ;
® marquage de t à partir de b : on a p t = min{p b , c(b, t) − f (b, t)} = min{4, 3} = 3
donc t reçoit la marque (b
+ , 3).
Augmentons le flot de la quantité p t = 3 sur le chemin (s, c, a, b, t) : il vient
f (b, t) = f (a, b) = f (c, a) = f (s, c) = 3 (phase III) et supprimons toutes les marques
sauf celle de s. On a obtenu le flot de la figure 5.
a
b
c
d
t
s
(1, 0)
(1, 0)
(2, 0)
(3, 0)
(3, 3)
(4, 0)
(4, 3)
(4, 3)
(5, 3)
figure 5
b) Marquons successivement les sommets c, b, d, t.
® marquage de c : la capacité de (s, c) est 4, donc p c = min{∞, 4} = 4 et c est
marqué (s
+ , 4) ;
® marquage de b à partir de c : la capacité de (c,b) est 1, donc p b = min{p c ,1} = 1
et b est marqué (c
+ , 1) ;
® marquage de d à partir de b : la capacité de (b,d) est 1, donc p d = min{p b ,1} = 1,
et d est marqué (b
+ , 1) ;
® marquage de t à partir de d : la capacité de (d,t) est 4, donc p t = min{p d ,4} = 1
et t est marqué (d
+ , 1).
On augmente le flot de 1 sur le chemin (s, c, b, d, t), en posant f (d, t) = f (b, d) =
f (c, b) = 1 et f (s, c) = 3 + 1 = 4 puis on supprime toutes les marques sauf celle
de s. Le flot obtenu est montré figure 6.
a
b
c
d
t
s
(1, 1)
(1, 1)
(2, 0)
(3, 0)
(3, 3)
(4, 1)
(4, 4)
(4, 3)
(5, 3)
figure 6
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 91