Solu tions des exer cices du cha pitre 4
469
© Dunod – Toute reproduction non autorisée est un délit.
4.11 Traçons le réseau de transport, puis éta -
blis sons d’abord un flot com plet, c’est- à-dire
pour lequel tout che min allant de la source O
au puits S, com porte au moins un arc saturé :
Pro cé dons ensuite au mar quage qui, dans le
cas de figure ci- dessus, abou tit à mar quer le
puits S du réseau. On sait que, dans ces condi -
tions, on n’a pas obtenu le flot maximal.
On voit que la chaîne OCHAEBFS ci-dessous,
extraite du graphe, se prête à des modi fi ca tions.
En res pec tant la loi de Kirchhoff, on pourra
aug men ter le flot total de 5 uni tés (le tran sport
de cer tains arcs est aug menté de 5, celui des
arcs diri gés dans le sens inverse du par cours
OS de la chaîne est dimi nué de 5).
La figure en bas de cette page tient compte des modi fi ca tions effec tuées sur la chaîne ; la pro -
cé dure de mar quage n’abou tit plus à S. On a donc une solu tion opti male (une autre solu tion
opti male évi dente sature toutes les des ti nations sauf E), de valeur 90.
On remar quera que la coupe (Γ), dont font par tie tous les sommets non mar qués, reçoit bien un flot
opti mal : tous les arcs allant de sommets mar qués vers des sommets non mar qués sont satu rés ; le
seul arc allant d’un sommet non mar qué à un sommet mar qué tran sporte un flot nul : c’est (B, H ).
NB : ci-dessus, les arcs en traits épais sont des arcs saturés.
D
D
E
F
S
0
O
O
B
0
0
B
-G
G
G
H
H
C
C
F
FLOT
OPTIMAL
COUPE
MINIMALE
( Γ)
Sommet marqués
Sommet non
marqués
10
10
10
10
25
5
30
20
15
15
40
5
5
5
5
15
25
20
A
A
E
S
+C
+A
+A
+O
+
Γ
Chaîne
améliorante