Définition
Un graphe est pondéré si l’on a associé à chaque arc
a, b un nombre réel w(a, b)
appelé le poids de l’arc. Le poids d’un chemin, ou d’un graphe, est la somme des
poids des arcs qui le composent.
Nous allons présenter trois problèmes classiques et leur algorithme de résolution.
3.1 Arbre de recouvrement de poids minimal
Exemple.
p 1 p 2 p 3 p 4 p 5
p 2 5
p 3 3 4
p 4 7 1 8
p 5 10 6 2 7
p 6 2 5 6 4 3
`
À partir d’une localité p 1 déjà raccordée au réseau du gaz, on veut
alimenter les localités p 2 , p 3 , . . . , p 6 . Le plan de distribution doit minimiser la longueur de conduite à poser.
Ci-contre le tableau des distances entre localités.
Formons le graphe G de sommets 1, . . . , 6 où deux
sommets quelconques sont toujours joints par un arc.
L’arc joignant i et j est pondéré par la distance d i,j
des localités p i et p j .
Un plan de distribution sera représenté par un sousgraphe T ayant les propriétés suivantes :
a) T doit contenir tous les sommets 1, 2, . . . , 6 ;
b) T n’a pas de cycle et entre deux sommets, il doit exister un chemin : autrement
dit, T est un arbre ;
c) parmi les arbres ayant les propriétés précédentes, T doit être de poids minimal.
Un sous-graphe T ayant les propriétés (a) et (b) s’appelle un arbre de recouvrement de G.
On va construire un arbre de recouvrement de poids minimal en sélectionnant au
fur et à mesure ses sommets et ses arcs.
I) Choisissons dans G un arc de poids minimal : l’arc
2, 4 , de poids 1, convient.
Les sommets 2 et 4, avec l’arc qui les joint, forment un arbre T 1 .
II) Considérons tous les arcs joignant l’un des sommets 2 ou 4 à un sommet qui n’est pas
dans T 1 , c’est-à-dire les arcs
1, 2 ,
1, 4 ,
3, 2 ,
3, 4 ,
5, 2 ,
5, 4 ,
6, 2 et
6, 4 . Les poids sont
d 1,2 d 1,4 d 3,2 d 3,4 d 5,2 d 5,4 d 6,2 d 6,4
5
7
4
8
6
7
5
4
Parmi ces arcs, l’arc
3, 2 est de poids minimal d 3,2 = 4. On l’ajoute à T 1 pour
former l’arbre T 2 de sommets {2, 4, 3} ayant pour arcs
4, 2 et
2, 3 .
III) Recommençons comme à l’étape précédente : voici les poids des arcs joignant l’un
des sommets de T 2 à un sommet qui n’est pas dans T 2 , c’est-à-dire à 1, 5 ou 6 :
d 1,2 d 1,3 d 1,4 d 5,2 d 5,3 d 5,4 d 6,2 d 6,3 d 6,4
5
3
7
6
2
7
5
6
4
80 – GRAPHES
Un graphe est pondéré si l’on a associé à chaque arc
a, b un nombre réel w(a, b)
appelé le poids de l’arc. Le poids d’un chemin, ou d’un graphe, est la somme des
poids des arcs qui le composent.
Nous allons présenter trois problèmes classiques et leur algorithme de résolution.
3.1 Arbre de recouvrement de poids minimal
Exemple.
p 1 p 2 p 3 p 4 p 5
p 2 5
p 3 3 4
p 4 7 1 8
p 5 10 6 2 7
p 6 2 5 6 4 3
`
À partir d’une localité p 1 déjà raccordée au réseau du gaz, on veut
alimenter les localités p 2 , p 3 , . . . , p 6 . Le plan de distribution doit minimiser la longueur de conduite à poser.
Ci-contre le tableau des distances entre localités.
Formons le graphe G de sommets 1, . . . , 6 où deux
sommets quelconques sont toujours joints par un arc.
L’arc joignant i et j est pondéré par la distance d i,j
des localités p i et p j .
Un plan de distribution sera représenté par un sousgraphe T ayant les propriétés suivantes :
a) T doit contenir tous les sommets 1, 2, . . . , 6 ;
b) T n’a pas de cycle et entre deux sommets, il doit exister un chemin : autrement
dit, T est un arbre ;
c) parmi les arbres ayant les propriétés précédentes, T doit être de poids minimal.
Un sous-graphe T ayant les propriétés (a) et (b) s’appelle un arbre de recouvrement de G.
On va construire un arbre de recouvrement de poids minimal en sélectionnant au
fur et à mesure ses sommets et ses arcs.
I) Choisissons dans G un arc de poids minimal : l’arc
2, 4 , de poids 1, convient.
Les sommets 2 et 4, avec l’arc qui les joint, forment un arbre T 1 .
II) Considérons tous les arcs joignant l’un des sommets 2 ou 4 à un sommet qui n’est pas
dans T 1 , c’est-à-dire les arcs
1, 2 ,
1, 4 ,
3, 2 ,
3, 4 ,
5, 2 ,
5, 4 ,
6, 2 et
6, 4 . Les poids sont
d 1,2 d 1,4 d 3,2 d 3,4 d 5,2 d 5,4 d 6,2 d 6,4
5
7
4
8
6
7
5
4
Parmi ces arcs, l’arc
3, 2 est de poids minimal d 3,2 = 4. On l’ajoute à T 1 pour
former l’arbre T 2 de sommets {2, 4, 3} ayant pour arcs
4, 2 et
2, 3 .
III) Recommençons comme à l’étape précédente : voici les poids des arcs joignant l’un
des sommets de T 2 à un sommet qui n’est pas dans T 2 , c’est-à-dire à 1, 5 ou 6 :
d 1,2 d 1,3 d 1,4 d 5,2 d 5,3 d 5,4 d 6,2 d 6,3 d 6,4
5
3
7
6
2
7
5
6
4
80 – GRAPHES