Graphes valués
Enseignante:
Olfa Layouni
E-mail:
1
Graphes valués
◼ Un graphe G = (S,A) est dit valué (ou pondéré) si on affecte à tous ses arcs
(cas non orienté) ou ses arêtes (cas orienté) des valeurs (poids) (ex: distance,
argent, durée, probabilité… ).
A
5
E
B
2
4
Advertisement
12
4
C
1
D
Plusieurs algorithmes supposent que les poids sont positifs ou nuls
2
Graphes valués
> Cas non orienté
⚫ Le poids d’une chaîne est la somme des poids des arêtes qui la composent.
⚫ La plus courte chaîne entre deux sommets est celle qui a le poids minimum
(parmi toutes les chaînes qui les relient).
⚫ La distance entre deux sommets est égale au poids de la chaîne la plus
courte les reliant
A
5
Advertisement
E
B
2
4
12
4
C
1
D
- Le poids de la chaîne (B,A,C,D,E) est 12
- Le poids de la chaîne (B,C,D,E) est 17
- Le poids de la chaîne (B,A,D,E) est 13
- La plus courte chaîne reliant B à E est la chaîne (B,A,C,D,E)
- La distance entre B et E est 12
3
Graphes valués
> Cas orienté
Le poids d’un chemin est la somme des poids des arcs qui le composent.
La plus court chemin entre deux sommets est celui qui a le poids minimum (parmi tous
les chemins qui les relient).
Advertisement
La distance entre deux sommet est égale au poids du chemin le plus court les reliant
- Le poids du chemin (A,C,B,E) est 5
- Le poids de la chemin (A,C, E) est 6
- Le poids de la chemin (A,D,E) est 8
- Le plus court chemin reliant A à E est (A,C,B,E)
- la distance entre A et E est égale à 5
- Pas de chemin entre E et A → le plus court chemin est inexistant
4
Graphes valués
> Représentation
Pour les graphes valués (orientés ou non):
⚫ Dans la matrice d’adjacences M(i,j)=poids de l’arc (ou l’arête)
⚫ Dans la liste d’adjacence on doit sauvegarder le poids de l’arcs (ou de
l’arête)
0
0
0
0
4.2
0
0
Advertisement
0
0
0
5.6
7.3
0
0
10.6
0
1: 2(4,2)
2: 3;4 (5,6;7,3)
3: 4 (10,6)
4: -