qui est un nombre strictement positif puisque γ est non saturé. Pour chaque arc du
graphe, on pose
ˆ
f (α) = f (α) + p(γ) si α est un arc direct de γ
ˆ
f (α) = f (α) − p(γ) si α est un arc indirect de γ
ˆ
f (α) = f (α) si α n’est pas un arc de γ.
On vérifie facilement que ˆ
f est encore un flot et que l’on a val( ˆ
f ) = val(f ) + p(γ).
Puisque p(γ) est strictement positif, on a val( ˆ
f ) > val(f ).
Pour le flot f de la figure 3, le chemin γ = (s, a, b, c, d, t) est non saturé : en effet, sur
les arcs directs, le flot est strictement inférieur à la capacité et sur l’arc indirect (c, b),
le flot est strictement positif. On a p(s, a) = p(a, b) = p(c, b) = p(c, d) = 1, p(d, t) = 2,
donc p(γ) = 1. On peut donc augmenter le flot de 1 sur les arcs directs (s, a), (a, b),
(c, d) et (d, t) et le diminuer de 1 sur (c, b) : on obtient le flot ˆ
f de la figure 4.
a
b
c
d
t
s
(1, 1)
(1, 0)
(2, 2)
(3, 3)
(3, 3)
(4, 3)
(4, 3)
(4, 4)
(5, 1)
figure 4
Recherche de chemins non saturés
Pour chercher des chemins non saturés, on utilise un procédé de marquage successif
des sommets du graphe. Voici la règle du marquage.
® La source s reçoit pour marque (−, ∞), où le signe ∞ représente un nombre très
grand par rapport aux capacités des arcs du graphe.
® Supposons que le sommet u a été marqué et que v est un sommet non marqué
adjacent à u.
marquage en avant : si l’arc orienté est (u, v) et si f (u, v) < c(u, v), on donne à
v la marque (u
+ , p v ), où p v = min {p u , c(u, v) − f (u, v)}.
marquage en arrière : si l’arc orienté est (v, u) et si f (v, u) > 0, on donne à v
la marque (u
− , p v ), où p v = min {p u , f(v, u)}.
Quand un sommet v a été marqué, on peut remonter jusqu’à la source les prédécesseurs de v dans le marquage : en effet, si la marque de v contient u
+ ou u
− , c’est que
le marquage de u a immédiatement précédé celui de v. Cela détermine un chemin
(s = a 0 , a 1 , a 2 , . . . , a k = v) où a i+1 a été marqué à partir de a i . Par construction, la
marque p v est strictement positive. Si v =t, on a obtenu un chemin non saturé de s à t.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 89
graphe, on pose
ˆ
f (α) = f (α) + p(γ) si α est un arc direct de γ
ˆ
f (α) = f (α) − p(γ) si α est un arc indirect de γ
ˆ
f (α) = f (α) si α n’est pas un arc de γ.
On vérifie facilement que ˆ
f est encore un flot et que l’on a val( ˆ
f ) = val(f ) + p(γ).
Puisque p(γ) est strictement positif, on a val( ˆ
f ) > val(f ).
Pour le flot f de la figure 3, le chemin γ = (s, a, b, c, d, t) est non saturé : en effet, sur
les arcs directs, le flot est strictement inférieur à la capacité et sur l’arc indirect (c, b),
le flot est strictement positif. On a p(s, a) = p(a, b) = p(c, b) = p(c, d) = 1, p(d, t) = 2,
donc p(γ) = 1. On peut donc augmenter le flot de 1 sur les arcs directs (s, a), (a, b),
(c, d) et (d, t) et le diminuer de 1 sur (c, b) : on obtient le flot ˆ
f de la figure 4.
a
b
c
d
t
s
(1, 1)
(1, 0)
(2, 2)
(3, 3)
(3, 3)
(4, 3)
(4, 3)
(4, 4)
(5, 1)
figure 4
Recherche de chemins non saturés
Pour chercher des chemins non saturés, on utilise un procédé de marquage successif
des sommets du graphe. Voici la règle du marquage.
® La source s reçoit pour marque (−, ∞), où le signe ∞ représente un nombre très
grand par rapport aux capacités des arcs du graphe.
® Supposons que le sommet u a été marqué et que v est un sommet non marqué
adjacent à u.
marquage en avant : si l’arc orienté est (u, v) et si f (u, v) < c(u, v), on donne à
v la marque (u
+ , p v ), où p v = min {p u , c(u, v) − f (u, v)}.
marquage en arrière : si l’arc orienté est (v, u) et si f (v, u) > 0, on donne à v
la marque (u
− , p v ), où p v = min {p u , f(v, u)}.
Quand un sommet v a été marqué, on peut remonter jusqu’à la source les prédécesseurs de v dans le marquage : en effet, si la marque de v contient u
+ ou u
− , c’est que
le marquage de u a immédiatement précédé celui de v. Cela détermine un chemin
(s = a 0 , a 1 , a 2 , . . . , a k = v) où a i+1 a été marqué à partir de a i . Par construction, la
marque p v est strictement positive. Si v =t, on a obtenu un chemin non saturé de s à t.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 89