Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
144
2) ou bien faire cir
cu ler un flux satu rant de 1 sur (O, D) et satu rer (D, b), repor ter
le flux satu rant de 1 de (E, b) à (E, d), ce qui sature (d, S).
3) Une troi sième pos si bi lité nous est offerte : Satu rer (A, b) et (O, D) ; ache mi ner
le flux de (O, D) sur (D, a) ; enfin repor ter le flux de (E, b) à (E, d), ce qui sature (d, S).
L’arc (D, e) ne per
met pas de modi fi
ca tion inté res sante, car le coût de l’arc (B, d) est
2 et non 0.
On a donc 3 solutions (de coût 10) : [A-a, B-e, C-c, D-b, E-d] ou
[A-b, B-e, C-c, D-a, E-d] ou [A-d, B-e, C-c, D-a, E-b].
Remarques.
1. Le lec teur pourra consta ter l’ana lo gie de cette méthode avec l’algo rithme
de Roy (Busacker- Gowen) pré senté au para graphe 4.5. En effet, un pro -
blème d’affec ta tion à coût mini mal peut être modé lisé par un pro blème de
flot maximal de coût mini mal. Le réseau de tran sport asso cié au pro blème
d’affec ta
tion est obtenu comme ci dessus (fig. 4.32) de la façon sui vante : la
source Ο du réseau a pour suc ces seurs les som mets cor res pon dant aux lignes
du tableau, le puits S a pour pré dé ces seurs les som mets cor res pon dant aux
colonnes ; tout som met cor res pon dant à une ligne a pour suc ces seurs tous
les som mets (qui cor res pon dent aux colonnes) ; ainsi à toute case du tableau
cor res pond un arc dans le réseau de tran sport ; les capa ci tés des arcs valent
toutes 1 ; les coûts uni taires asso ciés aux arcs sont les sui vants : 0 pour les
arcs ayant la source Ο pour ori gine ou le puits S pour extré mité ; le coût
p ij asso cié à l’arc (i, j) est le coef fi cient de la case situé sur la ligne i et la
colonne j du tableau ini tial des coûts.
L’affec ta tion par tielle don
née dans le tableau 4.4 cor
res pond au flot repré
senté par la figure 4.32. Ce flot est obtenu après 4 ité ra tions de l’algo
rithme
de Roy (Busacker- Gowen). À cha cune de ces ité ra tions, le che min de coût
mini
mal dans le graphe d’écart était de coût 0. À cette étape, le flot de valeur
4 n’est pas maxi mal. Le che min de coût mini mal dans le graphe d’écart, cor -
res pon
dant au flot repré senté par la figure 4.32, est le che min (O, D, b, E, d,
P) de coût 1. Le flot sui vant est alors de valeur maximale 5 et de coût mini
mal 10. Ce flot cor
res pond à l’affec
ta tion repré
sen
tée dans le tableau 4.7
2. La démons tra tion de la vali dité de l’algo rithme hon grois (ou « méthode
hon groise ») pré sente une ana lo gie inté res sante avec celle de l’algo rithme de
Ford- Fulkerson ; le lec teur inté ressé pourra se repor ter à [1].
4.7 notions d ’ Arbre et d ’ Arbo res cence
Nous appro fon
dis sons des notions que nous avions défi
nies au cha pitre 3.
Au préa
lable défi
nis sons le “nombre cyclomatique” d’un graphe G : V(G). Si G
com porte n som mets, m arcs et p com po santes connexes, on pose V 1 G2 5 m 2 n 1 p.
Par récur rence on peut mon trer que V 1 G2 5 0 si et seulement si G nra pas de cycle
et V1 G2 5 1 si et seulement si G com porte un cycle unique.
144
2) ou bien faire cir
cu ler un flux satu rant de 1 sur (O, D) et satu rer (D, b), repor ter
le flux satu rant de 1 de (E, b) à (E, d), ce qui sature (d, S).
3) Une troi sième pos si bi lité nous est offerte : Satu rer (A, b) et (O, D) ; ache mi ner
le flux de (O, D) sur (D, a) ; enfin repor ter le flux de (E, b) à (E, d), ce qui sature (d, S).
L’arc (D, e) ne per
met pas de modi fi
ca tion inté res sante, car le coût de l’arc (B, d) est
2 et non 0.
On a donc 3 solutions (de coût 10) : [A-a, B-e, C-c, D-b, E-d] ou
[A-b, B-e, C-c, D-a, E-d] ou [A-d, B-e, C-c, D-a, E-b].
Remarques.
1. Le lec teur pourra consta ter l’ana lo gie de cette méthode avec l’algo rithme
de Roy (Busacker- Gowen) pré senté au para graphe 4.5. En effet, un pro -
blème d’affec ta tion à coût mini mal peut être modé lisé par un pro blème de
flot maximal de coût mini mal. Le réseau de tran sport asso cié au pro blème
d’affec ta
tion est obtenu comme ci dessus (fig. 4.32) de la façon sui vante : la
source Ο du réseau a pour suc ces seurs les som mets cor res pon dant aux lignes
du tableau, le puits S a pour pré dé ces seurs les som mets cor res pon dant aux
colonnes ; tout som met cor res pon dant à une ligne a pour suc ces seurs tous
les som mets (qui cor res pon dent aux colonnes) ; ainsi à toute case du tableau
cor res pond un arc dans le réseau de tran sport ; les capa ci tés des arcs valent
toutes 1 ; les coûts uni taires asso ciés aux arcs sont les sui vants : 0 pour les
arcs ayant la source Ο pour ori gine ou le puits S pour extré mité ; le coût
p ij asso cié à l’arc (i, j) est le coef fi cient de la case situé sur la ligne i et la
colonne j du tableau ini tial des coûts.
L’affec ta tion par tielle don
née dans le tableau 4.4 cor
res pond au flot repré
senté par la figure 4.32. Ce flot est obtenu après 4 ité ra tions de l’algo
rithme
de Roy (Busacker- Gowen). À cha cune de ces ité ra tions, le che min de coût
mini
mal dans le graphe d’écart était de coût 0. À cette étape, le flot de valeur
4 n’est pas maxi mal. Le che min de coût mini mal dans le graphe d’écart, cor -
res pon
dant au flot repré senté par la figure 4.32, est le che min (O, D, b, E, d,
P) de coût 1. Le flot sui vant est alors de valeur maximale 5 et de coût mini
mal 10. Ce flot cor
res pond à l’affec
ta tion repré
sen
tée dans le tableau 4.7
2. La démons tra tion de la vali dité de l’algo rithme hon grois (ou « méthode
hon groise ») pré sente une ana lo gie inté res sante avec celle de l’algo rithme de
Ford- Fulkerson ; le lec teur inté ressé pourra se repor ter à [1].
4.7 notions d ’ Arbre et d ’ Arbo res cence
Nous appro fon
dis sons des notions que nous avions défi
nies au cha pitre 3.
Au préa
lable défi
nis sons le “nombre cyclomatique” d’un graphe G : V(G). Si G
com porte n som mets, m arcs et p com po santes connexes, on pose V 1 G2 5 m 2 n 1 p.
Par récur rence on peut mon trer que V 1 G2 5 0 si et seulement si G nra pas de cycle
et V1 G2 5 1 si et seulement si G com porte un cycle unique.