Arbres et arborescences
155
Sur l'exemple précédent, on joint d'abord
, puis
, puis
, puis
, puis
. Enfin, on ajoute l'arête
pour connecter le graphe. On retrouve bien l'arbre
partiel obtenu par l'algorithme de Kruskal.
Le problème de la recherche d'un arbre partiel minimal se pose souvent dans la pratique,
essentiellement lorsqu'il s'agit de dessin de réseaux, tels que voies de communications
entre villes, réseaux de pipelines, de galeries dans une mine etc.
Dans ces conditions, les sommets du graphe
représentent des points de passage
obligatoires de l'arbre partiel recherché. Cela dit, on peut encore améliorer l'arbre partiel
trouvé par une procédure type Kruskal ou Sollin en créant des sommets intermédiaires.
Par exemple, pour le graphe très simple suivant :
L'arbre partiel de valeur minimale est :
mais le réseau reliant les trois points et de longueur totale minimale est :
où le sommet créé est tel que l'on voit les trois côtés du triangle
sous un angle de
. On essaiera à chaque fois que l'on aura trouvé l'arbre partiel de valeur minimale,
de l'améliorer par l'addition de tels sommets intermédiaires. Les procédures pour y
A
B
C
A
B
C
A
B
C
120°