Exercices
185
V arBrEs, rEchErchEs arBo rEs cEnTEs
*4.16
On  consi    dère  le  graphe  valué  donné  par  la  figure  ci­     
contre  et  l’on  demande  de 
chercher l’arbre de valeur (ou “poids”) mini male :
1. par l’algo rithme de Prim, en respectant l’ordre alphabétique.
2. par l’algo rithme de Kruskal.
Existe­      t­il plu    sieurs solu    tions ?
*4.17
Résoudre  le  même  pro    blème  que  pré    cé    dem    ment  mais,  cette  fois,  afin  de  trou    ver 
l’arbre de valeur maximale.
**4.18
On demande de déter mi ner un cir cuit hamiltonien de valeur mini male dans le graphe
valué donné par la matrice des valeurs des arcs ci- dessous :
A B C D E
 1
0
1
2
0  4
3
5
1
1  4
0
4
7
2  1
0
1
2
0 
A
B
C
D
E
NB. Le lec teur trou vera d’autres exer cices por tant sur les recherches arbo res centes,
en fin du cha    pitre 1 : exer   
cices 1.4 et 1.6.