CHAPITRE 4 :
GRAPHE VALUÉ
Asma MEJRI
PLAN
I. GRAPHE VALUÉ
II. ALGORITHMES POUR LE GRAPHE VALUÉ
III. ALGORITHMES DU PLUS COURT CHEMIN
GRAPHE VALUÉ
GRAPHE VALUÉ
• Un graphe est valué lorsqu’à chaque arête ou arc est associé un nombre
réel.
• G=(X,A) est valué aux arêtes lorsqu’il existe une application v de A dans
IR , avec v(xy) est la valuation de l’arête {x,y}, c.à.d. lorsqu’à chaque
arête/ arc est associé un nombre réel / entier.
EXEMPLES
Graphe Orienté Graphe Non Orienté
a 12 b a 200 b
7 10 800
c c
v(ab)=12 v(ab)=200
v(ac)= 7 v(bc)=800
v(bc)=10
APPLICATIONS
• Trajets routiers : distance, temps de trajet, le coût
de déplacement …
• Réseaux de télécommunication : bande passante,
performance…
• Réseaux sociaux : fréquence des interactions,
force de liens sociaux
• Circuits électroniques : capacité, résistance…
DISTANCE
• La valeurs peuvent être des nombres négatifs. a -200 b
Exemple : transactions financières 400
• La valuation d’une chaîne/d’un chemin v(P) avec P est une chaine/ un chemin est la somme des
valuations de chacune de ses arêtes.
• La distance entre deux sommets x et y, notée d(x,y), d’un graphe valué aux arêtes est la valuation
minimale d’une chaine du graphe ayant ces deux sommets comme extrémités.
• Pour un graphe valué, la valuation est unitaire, v(a)=1 ∀ a ∈ A
EXEMPLE 1
a 3 c
3 3
1 3
e 1 s
v(ac)= 3
v(bd)= 5
1 1
b 5 d
Pour la chaîne, P=(e,a,c,b)
v(P)= 3+3+3+9
d(ec)=4
d(bd)=4 ≠ v(bd)
EXEMPLE 2
b 6 c
3
a 7
4
v(ab)=3
v(ae)= 5
5
e d
v(da)=3
6
3 d(ad)=11
ALGORITHMES POUR
LE GRAPHE VALUÉ
ALGORITHMES POUR LES GRAPHES VALUÉS
Problèmes courants pour les graphes valués
▪ Le plus court chemin (Dijkstra, Bellman Ford)
▪ Arbre recouvrant de poids minimal (Kruskal, Prim-Jarnick)
▪ Problèmes de flot maximal (Ford-Fulkerson)
ALGORITHME DE PLUS
COURT CHEMIN
PROBLÈME DU PLUS COURT CHEMIN
Les problèmes du Plus Court Chemin (PCC) ( chemin = trajet )
• Problème 1 (P1) : PCC entre deux sommets s et t donnés : d(s,t)
• Problème 2 (P2) : PCC à partir d’un sommet s ; d(s,v) ∀ v∈ X
• Problème 3 (P3) : PCC entre chaque paire de sommets s et t ; d(s,t) ∀ s,t ∈ X
(P2) permet de résoudre (P1) et (P3)
ALGORITHME DIJKSTRA
• Il permet de calculer la distance des sommets d’un graphe G par rapport à un
sommet donné.
• Il permet de trouver toutes les chaines/tous les chemins réalisant la distance
entre deux sommets.
• Les sommets sont visités dans l’ordre croissant de leur distance à partir du
sommet du départ.
• Il peut être appliqué pour les graphes connexes, orientés ou non orientés
EXERCICE
S
8 8
5
T 10 2 N Chercher le plus court chemin de M
L
à S dans le graphe G.
4 8 4
7
E 10 M
EXERCICE ▪ Dans la première colonne, il y a le numéro de l’itération, c’est le nombre de
passages dans la boucle « tant que »
▪ Dans la dernière colonne, il y a le sommet xn marqué en rouge à la nième itération,
Algorithme : Dijkstra avec entre parenthèse la valeur de la fonction d.
Données : Graphe G, ▪ Sur chaque ligne, les sommets marqués de tirets (----) sont les sommets rouges, ceux
Sommet M qui ont une distance finie sont les sommets verts, les autres n’ont pas encore été
Min ((10,M)
atteints.
Min ((7,M) ; Min ((12,N) Min ((11,L) ; Min ((14,E) ;
; (6+8,L)) (4+2,N)) ; (6+5,L)) (10+10,E)) (11+8,S))
Itération A partir de E L M N S T SOMMET
RETENU
0 initialisation +∞ +∞ (0,M) +∞ +∞ +∞ M (0,M)
1 M (10,M) (7,M) ----- (4,M) +∞ +∞ N (4,M)
2 N (10,M) (6,N) ----- ----- (12,N) +∞ L (6,N)
3 L (10,M) ----- ----- ----- (11,L) +∞ E (10,M)
4 E ----- ----- ----- ----- (11,L) (14,E) S (11,L)
5 S ----- ----- ----- ----- ----- (14,E) T (14,E)
On peut pour chaque itération k,
EXERCICE stocker les sommets verts dans un
arbre enraciné A ayant :
Résultat ▪ Chaque père a une distante d
inférieure ou égale à celle de ses fils.
• La distance du sommet M à S est 11. d(M,S)=11.
M 0
• La chaîne / les chaînes qui réalisent cette distance est/ sont : (M,N,L,S)
Remarques E 10 N 4
• Nous avons exploré tous les chemins possibles. 14
T L 6
• Il peut y avoir plusieurs chemins possibles.
S 11
• S’il y a des valeurs négatives, l’algorithme de Dijkstra ne marche pas.
RÉFÉRENCES
▪ Initiation à la théorie des graphes, Chrisitain Roux
▪ Introduction à la théorie des graphes, cours et exercices corrigés, Irène Larramendy
Valverde & Alain Marie-Jeanne
