Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
136
Soit l’arc (i, j) du réseau de tran sport ; dans le graphe d’écart G
e
F le coût de l’arc
(i, j) (qui existe si w ij , c ij ) est 1p ij et celui de l’arc (j, i) (qui existe si w ij . 0) est
2p ij . La figure 4.25 illustre cette construc tion ; le réseau de tran sport et le flot sont
repré sen tés à gauche, le graphe d’écart cor res pon dant est à droite.
Nous allons main te nant don ner, sans le démon trer, le théo rème de Roy four nis -
sant une condi tion néces saire et suf fi sante d’optimalité : un flot est de coût mini -
mal parmi les flots de valeur v(f), si et seule ment si il n’existe pas de cir cuit de coût
stric te ment néga tif dans G
e
F .
(NB. : ce théo rème est énoncé pour tout flot , n’est donc pas néces sai re ment
de valeur maximale.)
Figure 4.26 Un flot maximal de coût mini mal
Pour le flot maximal de coût 20 consi déré dans la figure 4.25, le cir cuit (A, S, B,
A) est de coût 25 : en vertu du théo rème pré cé dent, ce flot n’est donc pas de
coût
minimal. En effet le flot maximal repré senté dans la figure 4.26 est de coût 15. Ce
der nier flot est maximal car son graphe d’écart ne com porte pas de che min de S à P.
(NB : les coûts des cir cuits du graphe d’écart asso cié sont alors posi tifs ou nuls).
Nous allons don ner un algo rithme cal cu lant un flot maximal de coût mini mal dû à
B. Roy puis, indé pen dam ment, à R. Busacker et P. Gowen. Comme dans l’algo rithme
pré senté pour la recherche d’un flot de valeur maximale, à chaque étape de l’algo
rithme un flot est cal culé à par tir d’un flot F9 en uti li sant une chaîne amé lio rante
(cf 4.4.1). Le choix de la chaîne amé lio rante uti li sée fait que le graphe d’écart G
e
F
asso cié n’a pas de cir cuit de coût stric te ment néga tif. Cet algo rithme est le sui vant :
1. ini tia le ment F 5 (0, c , 0) ; G
e
F 5 R car on part du flot nul : w ij 5 0 pour tout
arc (i, j) ;
2. tant qu’il existe un che min de s à p dans G
e
F faire
3. déter mi ner C, un che min de coût mini mal de s à p
4. modi fier le flux sur tout arc (i, j) de C : si d 5 min
1i, j2 HC
r ij , le flux est aug menté de
d si (i, j) est un arc du réseau de tran sport ; le flux est dimi nué de d si (j, i) est
un arc du réseau de tran sport.
5.
tra cer le graphe d’écart G
e
F du flot ainsi modi fié.
136
Soit l’arc (i, j) du réseau de tran sport ; dans le graphe d’écart G
e
F le coût de l’arc
(i, j) (qui existe si w ij , c ij ) est 1p ij et celui de l’arc (j, i) (qui existe si w ij . 0) est
2p ij . La figure 4.25 illustre cette construc tion ; le réseau de tran sport et le flot sont
repré sen tés à gauche, le graphe d’écart cor res pon dant est à droite.
Nous allons main te nant don ner, sans le démon trer, le théo rème de Roy four nis -
sant une condi tion néces saire et suf fi sante d’optimalité : un flot est de coût mini -
mal parmi les flots de valeur v(f), si et seule ment si il n’existe pas de cir cuit de coût
stric te ment néga tif dans G
e
F .
(NB. : ce théo rème est énoncé pour tout flot , n’est donc pas néces sai re ment
de valeur maximale.)
Figure 4.26 Un flot maximal de coût mini mal
Pour le flot maximal de coût 20 consi déré dans la figure 4.25, le cir cuit (A, S, B,
A) est de coût 25 : en vertu du théo rème pré cé dent, ce flot n’est donc pas de
coût
minimal. En effet le flot maximal repré senté dans la figure 4.26 est de coût 15. Ce
der nier flot est maximal car son graphe d’écart ne com porte pas de che min de S à P.
(NB : les coûts des cir cuits du graphe d’écart asso cié sont alors posi tifs ou nuls).
Nous allons don ner un algo rithme cal cu lant un flot maximal de coût mini mal dû à
B. Roy puis, indé pen dam ment, à R. Busacker et P. Gowen. Comme dans l’algo rithme
pré senté pour la recherche d’un flot de valeur maximale, à chaque étape de l’algo
rithme un flot est cal culé à par tir d’un flot F9 en uti li sant une chaîne amé lio rante
(cf 4.4.1). Le choix de la chaîne amé lio rante uti li sée fait que le graphe d’écart G
e
F
asso cié n’a pas de cir cuit de coût stric te ment néga tif. Cet algo rithme est le sui vant :
1. ini tia le ment F 5 (0, c , 0) ; G
e
F 5 R car on part du flot nul : w ij 5 0 pour tout
arc (i, j) ;
2. tant qu’il existe un che min de s à p dans G
e
F faire
3. déter mi ner C, un che min de coût mini mal de s à p
4. modi fier le flux sur tout arc (i, j) de C : si d 5 min
1i, j2 HC
r ij , le flux est aug menté de
d si (i, j) est un arc du réseau de tran sport ; le flux est dimi nué de d si (j, i) est
un arc du réseau de tran sport.
5.
tra cer le graphe d’écart G
e
F du flot ainsi modi fié.