154
Recherche opérationnelle
Ainsi, si nous avons trois arêtes avec
on posera :
avec suffisamment petit pour ne pas modifier l'ordre des arêtes; une fois le calcul
effectué par la procédure exposée ci-dessus, on supprime le .
On démontre que l'on obtient bien ainsi un arbre partiel de valeur minimale (quel que
soit l'ordre dans lequel on augmente la valeur des arêtes équivalentes).
Appliquons cet algorithme à l'exemple suivant :
On obtient facilement :
2) Algorithme de Sollin
Dans l'algorithme de Sollin, on part d'un sommet arbitraire . On le joint au sommet le
plus proche (c'est-à-dire au sommet adjacent tel que l'arête reliant
à ce sommet soit de
valeur minimale parmi celles qui ont
pour sommet), soit . On prend alors un point
on le joint au sommet le plus proche, puis un point
que l'on
joint également au sommet le plus proche, etc... A la fin de cette procédure, on obtient
des sous-arbres qui peuvent être disjoints, soit et deux de ces sous-arbres. Comme
le graphe initial est connexe, il existe des arêtes de joignant
à . On les joint
alors par l'arête de plus faible valeur et on continue jusqu'à ce que les sous-arbres soient
tous reliés entre eux.
A
B
C
D
E
F
G
2,5
4
3
6
5
1,5
7
5,5
2
4
7
7
3
5
A
B
C
D
E
F
G
2,5
4
1,5
2
4
3