Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
140
Si l’on pou vait, dans le tableau 4.3 ainsi obtenu, choi sir un zéro par ligne et par
colonne, on aurait déjà la solu tion, mais ce n’est pas pos sible.
De plus, nous savons déjà que le « coût » de l’affec ta tion ne sera pas infé rieur à
9 (somme des chiffres ôtés aux dif fé rentes ran gées pour faire appa raître un zéro par
ligne : 5, puis par colonne : 4, cf tableaux 4.2 et 4.3).
Remarque. Le lec teur pour rait être tenté par l’énu mé ra tion des solu tions (qui,
ici, demeu re rait envi sa geable puisque 5 ! 5 120). Mais il devra se sou ve nir
que 10 ! atteint déjà 3 628 800 et qu’il fau drait plus de quatre mil lions de
siècles pour énu mé rer, à la vitesse d’un million de per mu ta tions par seconde,
les affec ta tions pos sibles sur un Tableau 25 3 25 (cf. cha pitre 2 sur la com -
plexité). L’algo rithme hon grois, exposé ci- dessous, per met de résoudre le pro -
blème en un temps rai son nable (même pour la dimen sion n 5 100).
Affec tons le zéro unique de la ligne A du tableau 4.3 ; nous ne pou vons plus
affec ter, sur la ligne B, que le zéro de la colonne e ; affec tons encore le zéro unique
de la ligne C ; nous ne pou vons plus affec ter aucun zéro de la ligne D, l’unique zéro
qu’elle conte nait ayant été exclu de l’affec ta tion par le choix du zéro de la ligne A ;
enfin, sur la ligne E, nous avons le choix entre le zéro de la colonne b et celui de la
colonne d ; rete nons, par exemple, le pre mier. Mais nous n’avons affecté que quatre
per sonnes, pas cinq…
Nous n’avons pas obtenu la solu tion, mais il convient de véri fier qu’il est impos
sible d’affec ter davan tage de zéros.
Pour cela, consi dé
rons le réseau de tran sport com
por tant une source fic tive O et
un puits fic tif S, dont les arcs, tous de capa cité 1, cor res pondent, entre les som mets
A, B, C, D, E, d’une part, et les som mets a, b, c, d et e, d’autre part, aux zéros du
tableau 4.3 (figure 4.32) ; les autres arcs relient O à A, B, C, D et E, ainsi que a, b, c,
d et e à S ; leur capa cité est 1.
Asso cions un flot dans ce réseau de tran
sport, à l’affec
ta tion par tielle ci dessus.
Ayant affecté les zéros comme au tableau 4.4, nous fixons à 1 le flux sur les arcs
(A, a), (B, e), (C, c) et (E, b), qui sont satu rés.
A
B
C
D
E
a b c d e
0 1 2 3 4
0 3 1 4 2
2 1 0 4 3
0 1 2 4 3
1 0 3 2 4
Tableau 4.2 On a sous trait 1 : le
plus petit élé ment de chaque ligne
A
B
C
D
E
a b c d e
0 1 2 1 2
0 3 1 2 0
2 1 0 2 1
0 1 2 2 1
1 0 3 0 2
Tableau 4.3 On a ensuite sous trait le
plus petit élé ment de chaque colonne
(2 en colonnes d et e)
140
Si l’on pou vait, dans le tableau 4.3 ainsi obtenu, choi sir un zéro par ligne et par
colonne, on aurait déjà la solu tion, mais ce n’est pas pos sible.
De plus, nous savons déjà que le « coût » de l’affec ta tion ne sera pas infé rieur à
9 (somme des chiffres ôtés aux dif fé rentes ran gées pour faire appa raître un zéro par
ligne : 5, puis par colonne : 4, cf tableaux 4.2 et 4.3).
Remarque. Le lec teur pour rait être tenté par l’énu mé ra tion des solu tions (qui,
ici, demeu re rait envi sa geable puisque 5 ! 5 120). Mais il devra se sou ve nir
que 10 ! atteint déjà 3 628 800 et qu’il fau drait plus de quatre mil lions de
siècles pour énu mé rer, à la vitesse d’un million de per mu ta tions par seconde,
les affec ta tions pos sibles sur un Tableau 25 3 25 (cf. cha pitre 2 sur la com -
plexité). L’algo rithme hon grois, exposé ci- dessous, per met de résoudre le pro -
blème en un temps rai son nable (même pour la dimen sion n 5 100).
Affec tons le zéro unique de la ligne A du tableau 4.3 ; nous ne pou vons plus
affec ter, sur la ligne B, que le zéro de la colonne e ; affec tons encore le zéro unique
de la ligne C ; nous ne pou vons plus affec ter aucun zéro de la ligne D, l’unique zéro
qu’elle conte nait ayant été exclu de l’affec ta tion par le choix du zéro de la ligne A ;
enfin, sur la ligne E, nous avons le choix entre le zéro de la colonne b et celui de la
colonne d ; rete nons, par exemple, le pre mier. Mais nous n’avons affecté que quatre
per sonnes, pas cinq…
Nous n’avons pas obtenu la solu tion, mais il convient de véri fier qu’il est impos
sible d’affec ter davan tage de zéros.
Pour cela, consi dé
rons le réseau de tran sport com
por tant une source fic tive O et
un puits fic tif S, dont les arcs, tous de capa cité 1, cor res pondent, entre les som mets
A, B, C, D, E, d’une part, et les som mets a, b, c, d et e, d’autre part, aux zéros du
tableau 4.3 (figure 4.32) ; les autres arcs relient O à A, B, C, D et E, ainsi que a, b, c,
d et e à S ; leur capa cité est 1.
Asso cions un flot dans ce réseau de tran
sport, à l’affec
ta tion par tielle ci dessus.
Ayant affecté les zéros comme au tableau 4.4, nous fixons à 1 le flux sur les arcs
(A, a), (B, e), (C, c) et (E, b), qui sont satu rés.
A
B
C
D
E
a b c d e
0 1 2 3 4
0 3 1 4 2
2 1 0 4 3
0 1 2 4 3
1 0 3 2 4
Tableau 4.2 On a sous trait 1 : le
plus petit élé ment de chaque ligne
A
B
C
D
E
a b c d e
0 1 2 1 2
0 3 1 2 0
2 1 0 2 1
0 1 2 2 1
1 0 3 0 2
Tableau 4.3 On a ensuite sous trait le
plus petit élé ment de chaque colonne
(2 en colonnes d et e)