Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
148
Sélec tion nons, par exemple, le som met a.
L’arête de valeur la plus faible adja cente à a est
[B, F], de valeur 2, qui relie a à b : on la retient.
Pre nons un som met, en dehors de {a, b} ; seul
reste g. L’arête de valeur la plus faible adja cente à g
est [F, G], de valeur 4 : on la retient.
On obtient fina le ment l’arbre de la figure 4.40, de
coût 16, en ajou tant [B, F] et [F, G] aux trois sous arbres de la figure 4.38.
Il y a d’autres solu tions de même coût : [F, G] peut être rem pla cée par [D, E]
(cf partie droite de la fig. 4.37) et [B, C] par [C, E].
Nous pré sen tons main te nant un der nier algo rithme, lui aussi très simple, dû à Prim :
1. mar quer arbi trai re ment un som met
2. tant qu’il existe un som met non mar qué faire
3. choi sir une arête de coût mini mal ayant une de ses deux extré mi tés mar quée et
l’autre non mar quée et l’inclure dans l’arbre en for ma tion ; mar quer cette autre
extré mité.
Il est aisé de mon trer que l’ensemble des arêtes choi sies à l’issue de l’algo rithme
consti tue un arbre de coût mini mal.
Un exemple d’exé cu tion de l’algo rithme est pré senté dans la figure 4.41 Les som
mets mar qués sont gri sés et les arêtes choi sies sont en trait épais. On a pris arbi trai -
re ment F comme som met ini tial.
L’arbre opti mal ainsi obtenu a pour valeur (ou coût) 16, comme avec l’algo rithme
de Kruskal et celui de Sollin. Mais il dif fère de l’arbre opti mal de Sollin ; cepen dant
en rem pla çant l’arête [F, G] dans la Fig 4.40, par l’arête [D, E] de même coût (égal à
4), on obtient l’arbre opti mal de Prim de la Fig 4.41 (qui est le même que celui fourni
par l’algo rithme de Kruskal).
En uti li sant des struc tures de don nées approp riées, la com plexité des algo rithmes
pré sen tés est O(m log m) pour l’algo rithme de Kruskal et O1 m 1 n log n 2 pour celui
dû à Prim. Le lec teur pourra consul ter [8] pour trou ver les argu ments jus ti fiant ces
com plexi tés.
Figure 4.38
Figure 4.39
Figure 4.40
148
Sélec tion nons, par exemple, le som met a.
L’arête de valeur la plus faible adja cente à a est
[B, F], de valeur 2, qui relie a à b : on la retient.
Pre nons un som met, en dehors de {a, b} ; seul
reste g. L’arête de valeur la plus faible adja cente à g
est [F, G], de valeur 4 : on la retient.
On obtient fina le ment l’arbre de la figure 4.40, de
coût 16, en ajou tant [B, F] et [F, G] aux trois sous arbres de la figure 4.38.
Il y a d’autres solu tions de même coût : [F, G] peut être rem pla cée par [D, E]
(cf partie droite de la fig. 4.37) et [B, C] par [C, E].
Nous pré sen tons main te nant un der nier algo rithme, lui aussi très simple, dû à Prim :
1. mar quer arbi trai re ment un som met
2. tant qu’il existe un som met non mar qué faire
3. choi sir une arête de coût mini mal ayant une de ses deux extré mi tés mar quée et
l’autre non mar quée et l’inclure dans l’arbre en for ma tion ; mar quer cette autre
extré mité.
Il est aisé de mon trer que l’ensemble des arêtes choi sies à l’issue de l’algo rithme
consti tue un arbre de coût mini mal.
Un exemple d’exé cu tion de l’algo rithme est pré senté dans la figure 4.41 Les som
mets mar qués sont gri sés et les arêtes choi sies sont en trait épais. On a pris arbi trai -
re ment F comme som met ini tial.
L’arbre opti mal ainsi obtenu a pour valeur (ou coût) 16, comme avec l’algo rithme
de Kruskal et celui de Sollin. Mais il dif fère de l’arbre opti mal de Sollin ; cepen dant
en rem pla çant l’arête [F, G] dans la Fig 4.40, par l’arête [D, E] de même coût (égal à
4), on obtient l’arbre opti mal de Prim de la Fig 4.41 (qui est le même que celui fourni
par l’algo rithme de Kruskal).
En uti li sant des struc tures de don nées approp riées, la com plexité des algo rithmes
pré sen tés est O(m log m) pour l’algo rithme de Kruskal et O1 m 1 n log n 2 pour celui
dû à Prim. Le lec teur pourra consul ter [8] pour trou ver les argu ments jus ti fiant ces
com plexi tés.
Figure 4.38
Figure 4.39
Figure 4.40