Arbres et arborescences
153
en essayant de supprimer les arêtes dans l'ordre de numérotation, on obtient :
Problème 2
Soit un graphe connexe
tel que toute arête u est associée à un nombre
, appelé valeur de l'arête. Trouver l'arbre partiel de de valeur totale minimale.
Il existe de nombreux algorithmes pour résoudre ce problème. Nous allons en donner
deux.
1) Algorithme de Kruskal.
Cet algorithme repose sur le résultat suivant : Si
est l'arbre de valeur minimale du
graphe
vérifie la condition :
Pour toute arête
, le cycle
créé en ajoutant
a toutes ses arêtes
telles que
Cette condition est évidente : en effet, en ajoutant
à , on crée bien un cycle
et un seul
; par ailleurs, les arêtes
de
appartiennent à . S'il existe un tel
que
, il suffit de remplacer par dans l'arbre pour obtenir un arbre de
valeur moindre que .
Dans ces conditions, l'arbre cherché, de valeur totale minimale contient nécessairement
l'arête de plus faible valeur; de même, il contient l'arête de valeur immédiatement
supérieure à celle de la précédente, à condition que ces deux arêtes ne forment pas un
cycle etc. C’est ce raisonnement qui est à la base de l'algorithme.
L'arbre partiel
de valeur minimale est obtenu en prenant pour
l'arête
de plus faible valeur, pour
l'arête de plus faible valeur différente de
et telle que
ne forment pas un cycle, pour l'arête de plus faible valeur différente de
et
et telle que
) ne forment pas un cycle etc. Lorsque toutes les arêtes ont des
valeurs différentes, l'arbre obtenu est évidemment unique.
Si certaines arêtes ont des valeurs identiques, il peut y avoir plusieurs solutions au
problème. Pour trouver une de ces solutions, il suffit de différencier légèrement les
arêtes de valeur identique.
B
A
E
D
C
6
7
8
9