Le poids minimal est obtenu pour l’arc
5, 3 de poids 2 : en ajoutant cet arc à T 2 ,
on obtient l’arbre T 3 qui a pour sommets 4, 2, 3, 5.
IV) Continuons de même : voici les poids des arcs joignant un sommet de T 3 à l’un
des sommets 1 ou 6 :
d 1,2 d 1,3 d 1,4 d 1,5 d 6,2 d 6,3 d 6,4 d 6,5
5
3
7
10
5
6
4
3
Comme arc de poids minimal, choisissons l’arc
1, 3 de poids 3. En ajoutant cet
arc à T 3 , on obtient l’arbre T 4 de sommets 4, 2, 3, 5, 1.
V)
T
T 3
T 2
4
2
5
3
4
2
5
3
4
2
3
1
4
(1)
(2) (3)
(4)
(2)
Il reste à sélectionner un arc de poids
minimal parmi ceux qui joignent le sommet 6 à un autre. C’est l’arc
6, 1 , de
poids 2, qui convient : en l’ajoutant à
T 4 , on obtient un arbre T solution :
il contient tous les sommets et est de
poids minimal 12.
Dans cet exemple, nous aurions pu, en II, choisir l’arc
4, 6 ; cela aurait conduit à l’un
des arbres T
ou T
différents de T mais de même poids total 12.
T
T
2
2
4
4
6
1
3
5
1
6
3
5
(1)
(1)
(3)
(2)
(2)
(2)
(2)
(4)
(4)
(3)
Construction d'un arbre de recouvrement de poids minimal
Soit G un graphe pondéré connexe. En numérotant les sommets de G, on peut supposer que l’ensemble des sommets est P = {1, 2, . . . , n}. Si i et j sont des sommets
adjacents, notons d i,j le poids de l’arc
i, j . Les sommets de l’arbre en construction
seront placés dans un ensemble S et les arcs dans un ensemble A. Le symbole ∞
désigne un nombre strictement supérieur à tous les poids des arcs de G.
Étape 1. Sélectionner dans G un arc de poids minimal ; si cet arc joint les sommets
a et b, on pose S = {a, b} et A =
a, b
.
Étape 2. Pour tout i ∈ P \ S ,
® s’il existe un arc joignant i à un sommet de S , trouver un sommet k i ∈ S tel
que d i,k i = min
j∈S
(d i,j ). Poser α i = d i,k i .
® s’il n’y a pas d’arc entre i et un sommet de S , poser α i = ∞.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 81