Une bonne programmation de l’automate doit lui permettre de passer au moindre
coût d’un état quelconque à un autre. Chaque arbre de recouvrement de poids
minimal apporte donc une réponse raisonnable à cette demande d’optimisation.
3.2 Chemin de poids minimum d'un sommet à un autre
Dans un graphe où la pondération des arcs représente par exemple des distances
ou des durées d’exécution de tâches, il est naturel de chercher les chemins les plus
courts possibles entre sommets.
Par exemple, en Linguistique, on définit des notions de proximité lexicale entre langues
d’un groupe donné. Si l’on forme un graphe dont les sommets représentent les langues
considérées et dont les arcs sont pondérés par la proximité, un chemin de poids minimal
entre deux sommets décrit les étapes d’une influence linguistique possible.
Exemple. Voici une table des temps de transport routier entre cinq localités
A, B, C, D, E (l’unité est le quart d’heure) ; la durée d’un trajet n’est pas forcément
le même dans un sens ou dans l’autre (à cause de la topographie, par exemple) ; le
signe ∞ indique qu’il n’y a pas de liaison directe entre les localités.
A B C D E
A 0
4
1 ∞ 6
B 5
0
3
6
2
C
1
1
0
4
4
D ∞ 2 10 0
9
E
1
1
3
7
0
Représentons ces données par un graphe à cinq sommets correspondant aux localités
A,B, C, D, E ; pour simplifier, nous numérotons dans cet ordre les sommets de 1 à 5.
Pour chaque paire de sommets i,j , il y a un arc muni de deux poids : le poids d(i,j)
est le temps de transport de i vers j et le poids d(j, i) est le temps de transport de
j vers i ; on donne au signe ∞ une très grande valeur, par exemple 1000.
Formons le tableau
D
0 =
⎡
⎢
⎢
⎢
⎣
0 4 1 1000 6
5 0 3 6 2
1 1 0 4 4
1000 2 10 0 9
1 1 3 7 0
⎤
⎥
⎥
⎥
⎦
Si i et j sont des entiers entre 1 et 5, on note D
0
i,j le nombre situé à l’intersection
de la i-ième ligne et de la j -ième colonne. Par exemple, D
0
2,4 = 6.
On va aussi utiliser des tableaux P à cinq lignes et cinq colonnes : le nombre P i,j ,
situé à l’intersection de la i-ième ligne et de la j -ième colonne de P , sera le numéro
du sommet qui suit le sommet i dans un plus court chemin de i vers j déjà découvert.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 83
coût d’un état quelconque à un autre. Chaque arbre de recouvrement de poids
minimal apporte donc une réponse raisonnable à cette demande d’optimisation.
3.2 Chemin de poids minimum d'un sommet à un autre
Dans un graphe où la pondération des arcs représente par exemple des distances
ou des durées d’exécution de tâches, il est naturel de chercher les chemins les plus
courts possibles entre sommets.
Par exemple, en Linguistique, on définit des notions de proximité lexicale entre langues
d’un groupe donné. Si l’on forme un graphe dont les sommets représentent les langues
considérées et dont les arcs sont pondérés par la proximité, un chemin de poids minimal
entre deux sommets décrit les étapes d’une influence linguistique possible.
Exemple. Voici une table des temps de transport routier entre cinq localités
A, B, C, D, E (l’unité est le quart d’heure) ; la durée d’un trajet n’est pas forcément
le même dans un sens ou dans l’autre (à cause de la topographie, par exemple) ; le
signe ∞ indique qu’il n’y a pas de liaison directe entre les localités.
A B C D E
A 0
4
1 ∞ 6
B 5
0
3
6
2
C
1
1
0
4
4
D ∞ 2 10 0
9
E
1
1
3
7
0
Représentons ces données par un graphe à cinq sommets correspondant aux localités
A,B, C, D, E ; pour simplifier, nous numérotons dans cet ordre les sommets de 1 à 5.
Pour chaque paire de sommets i,j , il y a un arc muni de deux poids : le poids d(i,j)
est le temps de transport de i vers j et le poids d(j, i) est le temps de transport de
j vers i ; on donne au signe ∞ une très grande valeur, par exemple 1000.
Formons le tableau
D
0 =
⎡
⎢
⎢
⎢
⎣
0 4 1 1000 6
5 0 3 6 2
1 1 0 4 4
1000 2 10 0 9
1 1 3 7 0
⎤
⎥
⎥
⎥
⎦
Si i et j sont des entiers entre 1 et 5, on note D
0
i,j le nombre situé à l’intersection
de la i-ième ligne et de la j -ième colonne. Par exemple, D
0
2,4 = 6.
On va aussi utiliser des tableaux P à cinq lignes et cinq colonnes : le nombre P i,j ,
situé à l’intersection de la i-ième ligne et de la j -ième colonne de P , sera le numéro
du sommet qui suit le sommet i dans un plus court chemin de i vers j déjà découvert.
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 83