4.8 Appli ca tions aux arbres opti maux
147
© Dunod – Toute reproduction non autorisée est un délit.
les arêtes sont les arêtes du graphe ini tial, sus cep tibles de connec ter deux à deux ces
sous arbres (elles ont la même valeur dans le graphe ini tial et dans le sous graphe).
Pas ser à a).
La vali dité de cet algo rithme est justifiée comme suit : la pro cé dure, qui est néces
sai re ment finie, ne peut engen drer que des sous
arbres (ou un arbre) puisque, à chaque
étape, on prend un som met x non encore retenu et donc on ne peut pas ainsi créer un
cycle. On montre, par l’absurde, qu’à chaque étape de l’algo rithme ces sous- arbres
sont opti maux. Fina le ment, on construit un arbre à par tir de ses sous- arbres opti maux.
Exemple. Consi dé rons un graphe G 5 (X, U ), dont les arêtes sont valuées par des
coûts ; on veut trou ver dans ce graphe, qui repré sente le pro jet d’un réseau de dis tri -
bu tion, un arbre de coût mini mal (fig. 4.37).
Figure 4.37
Opé rons selon l’algo rithme de Kruskal :
La liste par coûts croissants est : [B, E] : 1 ; [B, F] : 2 ; [A, F] : 3 ; [B, C] : 3 ; [C, E] :
3 ; [D, G] : 3 ; [E, F] : 3 ; [D, E] : 4 ; [F, G] : 4 ; etc.
La première arête choisie est [B, E] ; puis [B, F], puis [A, F], puis [B, C] ; on rejette
[C, E] qui forme un cycle avec les arêtes déjà retenues ; puis on prend [D, G], on
rejette [E, F], puis on prend [D, E] : fin car n 2 1 5 6 arêtes ont été retenues ; l’arbre
optimal a pour coût 16 (cf fig. 4.37, à droite).
Opé rons maintenant selon l’algo rithme de Sollin :
1) choix dans X de A : sélec tion de l’arête [A, F] ;
2) choix dans X 2 5A, F6 de B : sélec tion de l’arête [B, E] ;
3) choix dans X 2 5A, F, B, E6 de C : sélec tion de l’arête [C, B] ;
4) choix dans X 2 5A, F, B, E, C6 de D : sélec tion de l’arête [D, G].
La liste des som mets est épui sée : on a trois sous- arbres entre les quels sub siste un
cer tain nombre d’arêtes (ici, toutes les autres, sauf [C, E], qui, si on l’ajou tait, for me -
rait un cycle dans l’un des sous arbres) : cf fig. 4.38.
Nous dési gne rons main te nant par a, b et g les sous- arbres {A, F}, {B, C, E} et
{D, G}, consi dé rés désor mais comme les som mets d’un multi graphe (figures 4.38
et 4.39, avant et après « contrac tion »), formé par ces som mets et les arêtes qui les
relient entre eux. Ce sont, on le voit, toutes les arêtes autres que celles déjà rete nues,
à l’excep tion de [C, E] qui ne relie pas deux sous- arbres (et, pour cette rai son, ferme
un cycle dans {B, C, E}).
147
© Dunod – Toute reproduction non autorisée est un délit.
les arêtes sont les arêtes du graphe ini tial, sus cep tibles de connec ter deux à deux ces
sous arbres (elles ont la même valeur dans le graphe ini tial et dans le sous graphe).
Pas ser à a).
La vali dité de cet algo rithme est justifiée comme suit : la pro cé dure, qui est néces
sai re ment finie, ne peut engen drer que des sous
arbres (ou un arbre) puisque, à chaque
étape, on prend un som met x non encore retenu et donc on ne peut pas ainsi créer un
cycle. On montre, par l’absurde, qu’à chaque étape de l’algo rithme ces sous- arbres
sont opti maux. Fina le ment, on construit un arbre à par tir de ses sous- arbres opti maux.
Exemple. Consi dé rons un graphe G 5 (X, U ), dont les arêtes sont valuées par des
coûts ; on veut trou ver dans ce graphe, qui repré sente le pro jet d’un réseau de dis tri -
bu tion, un arbre de coût mini mal (fig. 4.37).
Figure 4.37
Opé rons selon l’algo rithme de Kruskal :
La liste par coûts croissants est : [B, E] : 1 ; [B, F] : 2 ; [A, F] : 3 ; [B, C] : 3 ; [C, E] :
3 ; [D, G] : 3 ; [E, F] : 3 ; [D, E] : 4 ; [F, G] : 4 ; etc.
La première arête choisie est [B, E] ; puis [B, F], puis [A, F], puis [B, C] ; on rejette
[C, E] qui forme un cycle avec les arêtes déjà retenues ; puis on prend [D, G], on
rejette [E, F], puis on prend [D, E] : fin car n 2 1 5 6 arêtes ont été retenues ; l’arbre
optimal a pour coût 16 (cf fig. 4.37, à droite).
Opé rons maintenant selon l’algo rithme de Sollin :
1) choix dans X de A : sélec tion de l’arête [A, F] ;
2) choix dans X 2 5A, F6 de B : sélec tion de l’arête [B, E] ;
3) choix dans X 2 5A, F, B, E6 de C : sélec tion de l’arête [C, B] ;
4) choix dans X 2 5A, F, B, E, C6 de D : sélec tion de l’arête [D, G].
La liste des som mets est épui sée : on a trois sous- arbres entre les quels sub siste un
cer tain nombre d’arêtes (ici, toutes les autres, sauf [C, E], qui, si on l’ajou tait, for me -
rait un cycle dans l’un des sous arbres) : cf fig. 4.38.
Nous dési gne rons main te nant par a, b et g les sous- arbres {A, F}, {B, C, E} et
{D, G}, consi dé rés désor mais comme les som mets d’un multi graphe (figures 4.38
et 4.39, avant et après « contrac tion »), formé par ces som mets et les arêtes qui les
relient entre eux. Ce sont, on le voit, toutes les arêtes autres que celles déjà rete nues,
à l’excep tion de [C, E] qui ne relie pas deux sous- arbres (et, pour cette rai son, ferme
un cycle dans {B, C, E}).