Solutions
478
On obtient ainsi le tableau 7, dont le coût total est seule ment 101 605, c’est- à-dire à moins
de 4 % de l’opti mum :
457
439
50
85
928
782
8
II
I
III
VII
IV
VIII
VI
800
1
1
2
2
3
3
4
4
5
V
1
1
2
354 �
85 �
8 �
�
50
800
542 �
�
�
�
�
928
2
3
3
4
4
5
�
tableau 7
en conclusion : la méthode de la différence maximale (Bales-hammer) est bien supérieure à la
méthode du coin nord-ouest (et aux méthodes «gourmandes» décrites en 4.9). lorsqu’elle ne fournit
pas l’optimum, elle donne une solution qui en est proche.
*4.16 1) Pour appli quer l’algo rithme de Prim, choi sis -
sons arbi trai re ment le som met A comme som met ini tial.
L’arête [A, B] est celle de poids le moins élevé issue de
A, elle est donc rete nue dans la solu tion. L’arête [H, B]
est rete nue dans la solu tion car elle est de poids mini mal
parmi celles ayant une et une seule extré mité dans {A, B}.
Ensuite [F, B] est sélec tion née, puis [F, E], [I, E], [I, D],
[E, G] et fina le ment [C, G]. La figure ci- contre repré sente
l’arbre opti mal de poids 22 obtenu. Il n’est pas unique.
2) Pas sons à l’algo rithme de Kruskal. À cet effet, éta blis sons la liste des arêtes par ordre
de valeurs crois santes : (pour sim pli fier : [X,Y] est noté XY)
BH : 1
: EI
: 1
: BF : 2
: AB : 2
CG : 3
: EG : 3
: AH : 4
: FH : 4
DI : 5
: EF : 5
: CD : 5
: DG : 6
DE : 6
: FI
: 7
: BG : 7
: CI : 8
AE : 8
: EH : 9
: CF : 9
: FG : 10
On prend suc ces si ve ment, dans l’ordre ci- dessus, les arêtes qui ne forment pas de cycle
avec les pré cé dentes : BH, EI, BF, AB, CG, EG, puis on éli mine AH et FH, qui forment des
cycles avec les pré cé dentes ; enfin, on retient DI et EF.
On retrouve la même solu tion que ci- dessus, mais on peut aussi rem pla cer DI par CD, de
même valeur : il existe plusieurs arbres optimaux.
*4.17 Appli quons l’algo rithme de Prim.
Choi sis sons le som met A comme som met ini tial. L’arête [A, E] est celle de poids le plus élevé
issue de A, elle est donc rete nue dans la solu tion. L’arête [H, E] est rete nue dans la solu tion
car elle est de poids maximal parmi celles ayant une et une seule extré mité dans {A, E}.
Ensuite [E, D] est sélec tion née, puis [G, D], [G, F], [F, C], [C, I] et fina le ment [B, G]. Nous
obte nons ainsi un arbre opti mal, de poids 63.
On calcule δ 32 = c 32 – c 12 + c 15 – c 35 = –44
La substitution porte sur v = 85 unités :
Pour cette solution δ 44 = –11. Le cycle de
substitution est donné ci-dessus. Cette substitution, avec v = 8, fournit le tab. 6 : l’optimum.
478
On obtient ainsi le tableau 7, dont le coût total est seule ment 101 605, c’est- à-dire à moins
de 4 % de l’opti mum :
457
439
50
85
928
782
8
II
I
III
VII
IV
VIII
VI
800
1
1
2
2
3
3
4
4
5
V
1
1
2
354 �
85 �
8 �
�
50
800
542 �
�
�
�
�
928
2
3
3
4
4
5
�
tableau 7
en conclusion : la méthode de la différence maximale (Bales-hammer) est bien supérieure à la
méthode du coin nord-ouest (et aux méthodes «gourmandes» décrites en 4.9). lorsqu’elle ne fournit
pas l’optimum, elle donne une solution qui en est proche.
*4.16 1) Pour appli quer l’algo rithme de Prim, choi sis -
sons arbi trai re ment le som met A comme som met ini tial.
L’arête [A, B] est celle de poids le moins élevé issue de
A, elle est donc rete nue dans la solu tion. L’arête [H, B]
est rete nue dans la solu tion car elle est de poids mini mal
parmi celles ayant une et une seule extré mité dans {A, B}.
Ensuite [F, B] est sélec tion née, puis [F, E], [I, E], [I, D],
[E, G] et fina le ment [C, G]. La figure ci- contre repré sente
l’arbre opti mal de poids 22 obtenu. Il n’est pas unique.
2) Pas sons à l’algo rithme de Kruskal. À cet effet, éta blis sons la liste des arêtes par ordre
de valeurs crois santes : (pour sim pli fier : [X,Y] est noté XY)
BH : 1
: EI
: 1
: BF : 2
: AB : 2
CG : 3
: EG : 3
: AH : 4
: FH : 4
DI : 5
: EF : 5
: CD : 5
: DG : 6
DE : 6
: FI
: 7
: BG : 7
: CI : 8
AE : 8
: EH : 9
: CF : 9
: FG : 10
On prend suc ces si ve ment, dans l’ordre ci- dessus, les arêtes qui ne forment pas de cycle
avec les pré cé dentes : BH, EI, BF, AB, CG, EG, puis on éli mine AH et FH, qui forment des
cycles avec les pré cé dentes ; enfin, on retient DI et EF.
On retrouve la même solu tion que ci- dessus, mais on peut aussi rem pla cer DI par CD, de
même valeur : il existe plusieurs arbres optimaux.
*4.17 Appli quons l’algo rithme de Prim.
Choi sis sons le som met A comme som met ini tial. L’arête [A, E] est celle de poids le plus élevé
issue de A, elle est donc rete nue dans la solu tion. L’arête [H, E] est rete nue dans la solu tion
car elle est de poids maximal parmi celles ayant une et une seule extré mité dans {A, E}.
Ensuite [E, D] est sélec tion née, puis [G, D], [G, F], [F, C], [C, I] et fina le ment [B, G]. Nous
obte nons ainsi un arbre opti mal, de poids 63.
On calcule δ 32 = c 32 – c 12 + c 15 – c 35 = –44
La substitution porte sur v = 85 unités :
Pour cette solution δ 44 = –11. Le cycle de
substitution est donné ci-dessus. Cette substitution, avec v = 8, fournit le tab. 6 : l’optimum.