de la source s vers le terminal t.
(2)
(2)
(2)
(1)
(3)
(3)
(4)
(1)
(5)
(7)
(6)
(4)
a
s
t
b
c
d
e
16. Recherche d'un flot admissible dans le cas de doubles contraintes. Soit G un graphe
orienté vérifiant les hypothèses faites page 87. Pour chaque arc α de G, on note
m(α) la capacité minimum de l’arc et M (α) sa capacité maximum, en supposant
0 m(α) M (α). Soit G
∗ le graphe orienté obtenu de la manière suivante :
® on ajoute à G deux sommets s
∗ et t
∗ ;
® pour chaque arc α = (u,v) de G, on ajoute un arc α
= (s
∗ ,v) et un arc α
= (u,t
∗ ) ;
® on définit les capacités sur G
∗ en posant, pour tout arc α = (u, v) de G :
c(α
) =
z∈G
m(z, v) , c(α
) =
z∈G
m(u, z) et c(α) = M (α) − m(α) ;
® on ajoute un arc (t, s) de « capacité infinie ».
s
∗
γ
γ
γ
β
β
s
a
b
t
t
∗
α
α
u
v
α
β
schéma de définition
du graphe G
∗
a) Vérifier que G
∗ est un graphe orienté ayant pour seule source s
∗ et pour seul
terminal t
∗ .
Un flot f
∗ sur G
∗ est dit saturant si l’on a f
∗ (α
) = c(α
) pour tout arc α de G.
b) Montrer qu’un flot saturant est un flot maximum sur G
∗ .
On suppose désormais que f
∗ est un flot saturant sur G
∗ . Pour tout arc α de G,
on pose f (α) = f
∗ (α) + m(α).
c) Montrer que l’on a m(α) f (α) M (α) pour tout arc α de G.
d) Montrer l’égalité
arc α de G f
∗ (α
) =
arc α de G f
∗ (α) =
arc α de G m(α).
e) En déduire que pour tout arc α de G, on a f
∗ (α
) = c(α
).
f) Soit u un sommet de G différent de s et de t. Montrer que l’on a
arc (y,u) de G f (y, u) =
arc (u,z) de G f (u, z) .
g) En déduire que f est un flot admissible sur G.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 99