c) Sur l’arc (s, c), le flot est égal à la capacité, donc on ne peut pas marquer c à
partir de s.
® Le sommet a est marquable : p a = c(s, a) − f (s, a) = 3, donc a reçoit la marque
(s
+ , 3). On peut alors marquer b, mais ensuite ni d ni t ne sont marquables,
car sur les arcs (b, d) et (b, t), le flot est égal à la capacité.
® À partir de a, on peut marquer c (marquage en arrière), car le flot de c vers
a est positif. On obtient p c = min{p a , 3} = 3 et c reçoit la marque (a
− , 3).
® On peut maintenant marquer successivement d et t : le sommet d est marqué
(c
+ , 2) et pour t, on a p t = min{p d , c(d, t) − f (d, t)} = min{2, 4 − 1} = 2, donc
la marque de t est (d
+ , 2).
Le chemin parcouru au cours du marquage est (s, a, c, d, t) ; sur les arcs directs
(d, t), (c, d) et (s, a), on augmente le flot de p t = 2 et sur l’arc indirect (c, a), on
diminue le flot de 2. On obtient le flot figure 7.
a
b
c
d
t
s
(1, 1)
(1, 1)
(2, 2)
(3, 2)
(3, 3)
(4, 3)
(4, 4)
(4, 3)
(5, 1)
figure 7
d) Sur l’arc (s, c), le flot est égal à la capacité, donc on ne peut pas marquer c à
partir de s. Le sommet a peut être marqué, car c(s, a) − f (c, a) = 3 − 2 = 1 > 0.
On peut aussi marquer b et c à partir de a. Mais sur les arcs (b, t), (b, d) et (c, d),
le flot est égal à la capacité : il sera donc impossible de marquer t. Les phases II,
III, IV de l’algorithme sont exécutées, donc le flot obtenu est maximum (figure 7).
La valeur du flot maximum est val(f ) = f (s, a) + f (s, c) = 2 + 4 = 6.
En faisant d’autres choix pour les marquages, on peut obtenir d’autres flots maximum
de même valeur, comme ceux de la figure 8.
a
b
c
d
t
s
(1, 1)
(1, 1)
(2, 2)
(3, 2)
(3, 3)
(4, 3)
(4, 3)
(4, 3)
(5, 0)
a
b
c
d
t
s
(1, 1)
(1, 0)
(2, 2)
(3, 2)
(3, 3)
(4, 3)
(4, 4)
(4, 4)
(5, 2)
figure 8
92 – GRAPHES