Étape 3. Trouver i
∗ tel que α i ∗ = min
j∈P \S
(α j ). Poser
S ← S ∪ {i
∗
} et A ← A ∪
i
∗ , k i ∗
.
Si l’ensemble S possède n éléments, alors l’arbre ayant pour arcs les éléments de
A est un arbre de recouvrement de poids minimal et l’algorithme est terminé.
Étape 4. Pour tout sommet i ∈ P \ S adjacent dans G à i
∗ et tel que d i,i ∗ < α i , poser
α i ← d i,i ∗ et k i ← i
∗ ,
puis retourner à l’étape 3.
Remarque
À l’étape 2, on a introduit le nombre α i dont la valeur est le plus petit poids d’un arc
reliant le sommet i∈P \S à l’un des sommets de S . Cela permet de diminuer le nombre
de comparaisons ultérieures entre poids. En effet, dans l’exemple précédent, la comparaison entre les poids d 1,2 et d 1,4 se fait en (II) : à l’issue de cette opération, on sait que le
plus petit des deux poids est d 1,2 ; en posant α 1 =d 1,2 =5, il suffira, en (III), de comparer
les nombres d 1,3 et α 1 ; la valeur k 1 =2 indique que c’est l’arc
1, 2 qui a le plus petit des
deux poids. On a de même k 3 =2, α 3 =d 3,2 =4, k 5 =2, α 5 =d 5,2 =2, k 6 =4 et α 6 =d 6,4 =4.
Quand on ajoute à S un nouveau sommet s, on peut être amené ensuite à considérer
un arc
i, s de poids inférieur à la valeur α i : c’est pourquoi, dans l’étape 4, on
donne dans ce cas à α i la valeur d i,s avant de retourner à l’étape 3.
Exemples d'application. La recherche d’un arbre de recouvrement de poids
minimal se rencontre dans de nombreux problèmes. Nous avons déjà mentionné l’organisation d’un service de distribution (courrier, marchandises, information) ; voici
deux autres exemples.
® En Biologie, on cherche à construire des arbres phylogéniques : ces arbres décrivent
les relations de parenté entre les organismes d’un groupe sélectionné et permettent
de faire des hypothèses en théorie de l’évolution.
On choisit un ensemble de caractères morphologiques ou génétiques et l’on forme
un graphe pondéré : les sommets représentent les organismes considérés et le
poids d’un arc entre deux organismes reflète l’écart entre leurs caractères, par
exemple au moyen d’un indice fondé sur la fréquence et la stabilité de certaines
mutations génétiques. Si l’on suppose que l’évolution des organismes se fait le
plus probablement au moindre coût génétique, alors un arbre de recouvrement de
poids minimal renseigne sur l’ordre dans lequel les mutations ont pu se produire.
® La Robotique conçoit des automates électro-mécaniques programmables pour des
tâches spécifiques. Leur fonctionnement se modélise aisément par un graphe : un
sommet représente un état de l’automate et un arc est une transition directe entre
deux états. Pour pondérer les arcs, on peut utiliser par exemple la durée de la
transition ou l’énergie consommée.
82 – GRAPHES
∗ tel que α i ∗ = min
j∈P \S
(α j ). Poser
S ← S ∪ {i
∗
} et A ← A ∪
i
∗ , k i ∗
.
Si l’ensemble S possède n éléments, alors l’arbre ayant pour arcs les éléments de
A est un arbre de recouvrement de poids minimal et l’algorithme est terminé.
Étape 4. Pour tout sommet i ∈ P \ S adjacent dans G à i
∗ et tel que d i,i ∗ < α i , poser
α i ← d i,i ∗ et k i ← i
∗ ,
puis retourner à l’étape 3.
Remarque
À l’étape 2, on a introduit le nombre α i dont la valeur est le plus petit poids d’un arc
reliant le sommet i∈P \S à l’un des sommets de S . Cela permet de diminuer le nombre
de comparaisons ultérieures entre poids. En effet, dans l’exemple précédent, la comparaison entre les poids d 1,2 et d 1,4 se fait en (II) : à l’issue de cette opération, on sait que le
plus petit des deux poids est d 1,2 ; en posant α 1 =d 1,2 =5, il suffira, en (III), de comparer
les nombres d 1,3 et α 1 ; la valeur k 1 =2 indique que c’est l’arc
1, 2 qui a le plus petit des
deux poids. On a de même k 3 =2, α 3 =d 3,2 =4, k 5 =2, α 5 =d 5,2 =2, k 6 =4 et α 6 =d 6,4 =4.
Quand on ajoute à S un nouveau sommet s, on peut être amené ensuite à considérer
un arc
i, s de poids inférieur à la valeur α i : c’est pourquoi, dans l’étape 4, on
donne dans ce cas à α i la valeur d i,s avant de retourner à l’étape 3.
Exemples d'application. La recherche d’un arbre de recouvrement de poids
minimal se rencontre dans de nombreux problèmes. Nous avons déjà mentionné l’organisation d’un service de distribution (courrier, marchandises, information) ; voici
deux autres exemples.
® En Biologie, on cherche à construire des arbres phylogéniques : ces arbres décrivent
les relations de parenté entre les organismes d’un groupe sélectionné et permettent
de faire des hypothèses en théorie de l’évolution.
On choisit un ensemble de caractères morphologiques ou génétiques et l’on forme
un graphe pondéré : les sommets représentent les organismes considérés et le
poids d’un arc entre deux organismes reflète l’écart entre leurs caractères, par
exemple au moyen d’un indice fondé sur la fréquence et la stabilité de certaines
mutations génétiques. Si l’on suppose que l’évolution des organismes se fait le
plus probablement au moindre coût génétique, alors un arbre de recouvrement de
poids minimal renseigne sur l’ordre dans lequel les mutations ont pu se produire.
® La Robotique conçoit des automates électro-mécaniques programmables pour des
tâches spécifiques. Leur fonctionnement se modélise aisément par un graphe : un
sommet représente un état de l’automate et un arc est une transition directe entre
deux états. Pour pondérer les arcs, on peut utiliser par exemple la durée de la
transition ou l’énergie consommée.
82 – GRAPHES