Exemple. Reprenons le graphe de l’exemple présenté en introduction. Sur la figure
suivante, nous indiquons à coté de chaque arc un couple capacité, flux : pour l’arc
(s, a), on a ainsi c(s, a) = 3 et f (s, a) = 2. C’est un exemple de flot ; sa valeur est
val(f ) = f (s, a) + f (s, b) = 4 = f (b, t) + f (d, t).
a
b
c
d
t
s
(1, 0)
(1, 1)
(2, 1)
(3, 2)
(3, 3)
(4, 1)
(4, 2)
(4, 2)
(5, 0)
figure 2
Procédé d'augmentation d'un flot
Supposons que f est un flot (par exemple f (u, v) = 0 pour tout arc (u, v)).
Rappelons qu’un chemin de G est une suite de sommets adjacents deux à deux différents. Dans un chemin de G, il y a en général des arcs parcourus dans le sens de
leur orientation et des arcs parcourus dans l’autre sens ; les premiers sont dits directs,
les autres sont indirects. Par exemple, dans le cas du graphe de la figure 1, le chemin
(s, a, b, c, d, t) a pour arcs directs (s, a), (a, b), (c, d) et (d, t) et l’arc (c, b) est indirect.
Supposons que γ est un chemin de s vers t dont tous les arcs sont directs et vérifient
f (u, v) < c(u, v). Si p est le minimum des différences c(u, v) − f (u, v) le long de γ ,
on peut augmenter le flot de la valeur p sur tous les arcs du chemin, car la loi de
conservation sera encore satisfaite après cette opération.
Par exemple, sur la figure 2, on peut augmenter le flot de 1 le long du chemin
(s, c, a, b, d, t) ; le résultat est montré figure 3.
a
b
c
d
t
s
(1, 1)
(1, 1)
(2, 1)
(3, 2)
(3, 3)
(4, 2)
(4, 3)
(4, 3)
(5, 1)
figure 3
Plus généralement, nous dirons qu’un chemin est non saturé si l’on a f (u, v) < c(u, v)
pour tous les arcs directs et f (u, v) > 0 pour tous les arcs indirects.
Supposons que γ est un chemin non saturé de s vers t. Pour tout arc α de γ , on pose
p(α) =
c(α) − f (α) si α est direct
f (α)
si α est indirect.
On définit
p(γ) = min
arc α de γ
{p(α)}
88 – GRAPHES