Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
168
La matrice 16 est de for mat 1 3 1 : se
gar der d’inter dire l’arc (E, C).
6. Prendre (E, C).
Borne de NON 1 E, C 2 5 23 1 ` 5 1`.
Borne de 1 E, C 2 5 23 1 0 5 23.
On a le cir cuit hamiltonien : (B, D, F, E, C, A, B), de valeur 23.
6 bis. On remarque que la borne du som met (A, E) est éga le ment 23 ; au numéro 5,
on a d’ailleurs choisi de conti nuer en pre nant (E, C) parce que la matrice 16 était de
for mat 1 3 1.
Il se pour rait donc qu’il existe un autre cir cuit hamiltonien uti li sant l’arc (A,
E). Reve nant à la matrice 7 bis, on éva lue les regrets de ses zéros et l’on choi sit
ainsi l’arc (C, A). On a ensuite : borne de NON 1 C, A2 5 23 1 6 5 29 et borne de
1 C, A2 5 23 1 1 5 24.
Matrice 18.
Matrice 18 bis.
Matrice 17 regrets.
A
0
0
2
6
1
1
C F
B
D
C
E
F
C F
E
D
1
0
0
0
0
2
1
B
F
C F
E
D
0
0
0
0
0
1
B
F
Toutes les autres bornes des som mets pen dants de l’arbo res cence étant main te -
nant stric te ment supé rieures à 23, on est sûr que le cir cuit opti mal trouvé en 6. est
unique.
La figure 4.49 repré
sente l’arbo
res cence par cou rue ; elle est rela ti ve ment peu
éten due par rap port à l’arbo res cence « poten tielle », celle asso ciée aux 1 6 2 12 !, soit
120 cir cuits hamiltoniens.
Remarque. Une méthode « gour mande » pour résoudre de manière appro -
chée (heuristiquement) cet exemple consis te rait à choi sir un arc de plus
petit coût, soit (A, E) de coût 1, puis, sans remettre en cause ce choix,
choi sir un arc de plus petit coût com pa tible avec (A, E) : (D, F) de coût 1,
et ainsi de suite. On choi sit ensuite (B, D) de coût 2, puis (C, A) de coût 5 ;
on doit alors obli ga toi re ment prendre les arcs (chers !) (E, B) de coût 7 et
(F, C) de coût 8, pour fer mer un cir cuit hamiltonien : (A, E, B, D, F, C, A)
de coût 24, non optimal.
Certes sur cet exemple, l’heu ris tique gour mande a fourni une solu tion proche
de l’opti mum : ce n’est pas le cas en géné ral, même sur des graphes de petite
taille. Ainsi, pour l’exemple ci- dessous, cf. Matrice 19, cette méthode gour -
mande four nit le cir cuit hamiltonien (A, B, D, C, A) de coût 103... alors que
l’opti mum (A, D, B, C, A) a pour coût seule ment 5.
Matrice 15.
regrets
Matrice 16.
C
C
C
A
0
E
E
168
La matrice 16 est de for mat 1 3 1 : se
gar der d’inter dire l’arc (E, C).
6. Prendre (E, C).
Borne de NON 1 E, C 2 5 23 1 ` 5 1`.
Borne de 1 E, C 2 5 23 1 0 5 23.
On a le cir cuit hamiltonien : (B, D, F, E, C, A, B), de valeur 23.
6 bis. On remarque que la borne du som met (A, E) est éga le ment 23 ; au numéro 5,
on a d’ailleurs choisi de conti nuer en pre nant (E, C) parce que la matrice 16 était de
for mat 1 3 1.
Il se pour rait donc qu’il existe un autre cir cuit hamiltonien uti li sant l’arc (A,
E). Reve nant à la matrice 7 bis, on éva lue les regrets de ses zéros et l’on choi sit
ainsi l’arc (C, A). On a ensuite : borne de NON 1 C, A2 5 23 1 6 5 29 et borne de
1 C, A2 5 23 1 1 5 24.
Matrice 18.
Matrice 18 bis.
Matrice 17 regrets.
A
0
0
2
6
1
1
C F
B
D
C
E
F
C F
E
D
1
0
0
0
0
2
1
B
F
C F
E
D
0
0
0
0
0
1
B
F
Toutes les autres bornes des som mets pen dants de l’arbo res cence étant main te -
nant stric te ment supé rieures à 23, on est sûr que le cir cuit opti mal trouvé en 6. est
unique.
La figure 4.49 repré
sente l’arbo
res cence par cou rue ; elle est rela ti ve ment peu
éten due par rap port à l’arbo res cence « poten tielle », celle asso ciée aux 1 6 2 12 !, soit
120 cir cuits hamiltoniens.
Remarque. Une méthode « gour mande » pour résoudre de manière appro -
chée (heuristiquement) cet exemple consis te rait à choi sir un arc de plus
petit coût, soit (A, E) de coût 1, puis, sans remettre en cause ce choix,
choi sir un arc de plus petit coût com pa tible avec (A, E) : (D, F) de coût 1,
et ainsi de suite. On choi sit ensuite (B, D) de coût 2, puis (C, A) de coût 5 ;
on doit alors obli ga toi re ment prendre les arcs (chers !) (E, B) de coût 7 et
(F, C) de coût 8, pour fer mer un cir cuit hamiltonien : (A, E, B, D, F, C, A)
de coût 24, non optimal.
Certes sur cet exemple, l’heu ris tique gour mande a fourni une solu tion proche
de l’opti mum : ce n’est pas le cas en géné ral, même sur des graphes de petite
taille. Ainsi, pour l’exemple ci- dessous, cf. Matrice 19, cette méthode gour -
mande four nit le cir cuit hamiltonien (A, B, D, C, A) de coût 103... alors que
l’opti mum (A, D, B, C, A) a pour coût seule ment 5.
Matrice 15.
regrets
Matrice 16.
C
C
C
A
0
E
E