Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
132
Si nous dési rons amé lio rer le flot, il fau dra aug men ter les flux tran spor tés par
(O, A), (A, E), (B, D) et (D, P) (les arcs de la chaîne amé lio rante qui ont donné lieu à un
mar quage 1), mais il fau dra dimi nuer d’autant le flux tran sporté par (B, E) (arc de la
chaîne amé lio rante ayant donné lieu à un mar quage -), de manière qu’aux som mets A,
Ε, B et D, la loi Kirchhoff conti nue d’être res pec tée. Nous voyons immé dia te ment que
l’on ne peut dimi nuer le flot de (B, E) que de 5 1/s ; par consé quent, nous ne pou vons
aug men ter les flux de cha cun des autres arcs que de 5 1/s et c’est pos sible parce que la
dif fé rence entre la capa cité et la quan tité tran spor tée est supé rieure à 5 pour tous ces
arcs (il suf fi rait qu’elle soit égale) : le cal
cul donne d
1 5 10 et d
2 5 5. D’où d 5 5.
Effec
tuons cette modi fi ca tion sur le flot ci
dessus ; pour les arcs directs :
fr u 5 f u 1 d et pour l’arc indirect : fr u 5 f u 2 d ; on obtient la figure 4.24. On
obtient un nou veau flot f9, de valeur V(f9) 5 85. Appli quons la pro cé dure de
mar quage à ce nou veau flot ; on ne peut pas mar quer le puits P : le flot obtenu est de
valeur maximale. Si l’on vou lait satis faire toutes les demandes, on pour rait aug men -
ter le débit maximal de la cana li sa tion AD d’au moins 5 1/s.
Bien que nous ne don nions que plus loin la démons tra tion de l’algo rithme, nous
allons déjà nous rendre compte qu’il conduit bien à une solu tion opti male. Consi dé rons
une ligne fer mée (ou coupe), à l’inté rieur de laquelle sont tous les som mets mar qués.
Vers l’exté rieur de cette courbe ne sortent que des arcs satu rés (NB : l’arc (B, D) ayant
son extré mité ini tiale et son extré mité ter mi nale à l’exté rieur de la courbe, ne doit être
consi déré ni comme arc sor tant, ni comme arc entrant) ; vers l’inté rieur de cette courbe
ne pénètrent que des arcs de flux nul, ici un seul (l’arc (B, E)). Il est évi dem ment impos -
sible de faire sor tir un flot de valeur supé rieure à celui qui est indi qué, puisque tous les
arcs sor tants sont satu rés et qu’il est impos sible de réduire le flot entrant, puisqu’il est nul.
Comme la courbe contient la source O, c’est bien le flot maximal qui part de la source.
Figure 4.24 Flot de valeur maximale et coupe de valeur mini male.
NB. Sur cet exemple, l’optimum est obtenu en une seule itération. Bien entendu,
dans le cas général, il peut y en avoir plusieurs.
132
Si nous dési rons amé lio rer le flot, il fau dra aug men ter les flux tran spor tés par
(O, A), (A, E), (B, D) et (D, P) (les arcs de la chaîne amé lio rante qui ont donné lieu à un
mar quage 1), mais il fau dra dimi nuer d’autant le flux tran sporté par (B, E) (arc de la
chaîne amé lio rante ayant donné lieu à un mar quage -), de manière qu’aux som mets A,
Ε, B et D, la loi Kirchhoff conti nue d’être res pec tée. Nous voyons immé dia te ment que
l’on ne peut dimi nuer le flot de (B, E) que de 5 1/s ; par consé quent, nous ne pou vons
aug men ter les flux de cha cun des autres arcs que de 5 1/s et c’est pos sible parce que la
dif fé rence entre la capa cité et la quan tité tran spor tée est supé rieure à 5 pour tous ces
arcs (il suf fi rait qu’elle soit égale) : le cal
cul donne d
1 5 10 et d
2 5 5. D’où d 5 5.
Effec
tuons cette modi fi ca tion sur le flot ci
dessus ; pour les arcs directs :
fr u 5 f u 1 d et pour l’arc indirect : fr u 5 f u 2 d ; on obtient la figure 4.24. On
obtient un nou veau flot f9, de valeur V(f9) 5 85. Appli quons la pro cé dure de
mar quage à ce nou veau flot ; on ne peut pas mar quer le puits P : le flot obtenu est de
valeur maximale. Si l’on vou lait satis faire toutes les demandes, on pour rait aug men -
ter le débit maximal de la cana li sa tion AD d’au moins 5 1/s.
Bien que nous ne don nions que plus loin la démons tra tion de l’algo rithme, nous
allons déjà nous rendre compte qu’il conduit bien à une solu tion opti male. Consi dé rons
une ligne fer mée (ou coupe), à l’inté rieur de laquelle sont tous les som mets mar qués.
Vers l’exté rieur de cette courbe ne sortent que des arcs satu rés (NB : l’arc (B, D) ayant
son extré mité ini tiale et son extré mité ter mi nale à l’exté rieur de la courbe, ne doit être
consi déré ni comme arc sor tant, ni comme arc entrant) ; vers l’inté rieur de cette courbe
ne pénètrent que des arcs de flux nul, ici un seul (l’arc (B, E)). Il est évi dem ment impos -
sible de faire sor tir un flot de valeur supé rieure à celui qui est indi qué, puisque tous les
arcs sor tants sont satu rés et qu’il est impos sible de réduire le flot entrant, puisqu’il est nul.
Comme la courbe contient la source O, c’est bien le flot maximal qui part de la source.
Figure 4.24 Flot de valeur maximale et coupe de valeur mini male.
NB. Sur cet exemple, l’optimum est obtenu en une seule itération. Bien entendu,
dans le cas général, il peut y en avoir plusieurs.