Théorie des graphes : Correction td 5 graphe s1 s5
Télécharger PDFphilippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Chemin optimal
Math ́ematiques
TD n◦ 5
Exercice1
Algorithme de Dijkstra
Appliquer l’algorithme de Dijkstra aux graphes suivant pour calculer les chemins de poids
minimum depuiss= 1 :1 2345 62 146 42 315 412 345 67 410 14 210 45 13 Exercice2 Algorithme de Bellman simplifi ́e
D ́ecomposer les graphes suivants en ni-
veaux puis appliquer l’algorithme de
Bellman simplifi ́e pour calculer les che-
mins de poids minimum et maximum
depuiss= 5 :12 34 56 78 241 −1−3 73 22 −10 123 456 78 58 25 10−1 149 4664 11 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Chemin optimal
Math ́ematiques
TD n◦ 5
Exercice3
Algorithme de Bellman-Ford
Appliquer l’algorithme de Bellman-Ford pour calculer les distances minimale depuis le
sommet colori ́e. Dans chaque cas, quel autre algorithme aurait on pu utiliser ? Pourquoi ?1 23 456 43 301 472 1−1 212 34 567 84 2321 31 22 317 Exercice4 Potentiel et distances minimales [DS 2010, 11pts]
SoitG= (S, A, W) un graphe orient ́e valu ́e (les poids des arcs seront repr ́esent ́es par
une matrice carr ́eeW), on appelle matrice des poids d’une applicationπdeSdansR, la
matriceMd ́efinie par :
∀(x, y)∈A, M(x, y) =π(y)−π(x)(1)
on dira alors queπest un potentiel deGsi :
∀(x, y)∈A, W(x, y)≥M(x, y)(2)
1. SoientGle graphe ci-dessous et les fonctionsπ 1
, π2 :S−→Rd ́efinies par :π 1
(1) = 13;π1 (2) =−2;π1 (3) = 0;π 1
(4) = 5;π1 (5) =−1π 2
(1) = 2;π2 (2) = 1;π 2
(3) = 2;π2 (4) = 3;π2 (5) = 01 23 45 17 −51 2−2 −4
(a) Calculer les matrices des poidsW, pour le grapheG, etM2 pourπ2 .
Indication :pour la fonctionπ1 le calcul de la matrice des poids donneM 1= 0−15−13−8−14
15 027 113−2 05−1 8−7−5 0−614−1 16 0
(b) ComparerWaux matricesM1 etM2 pour pouvoir en d ́eduire si les fonctionsπ 1etπ 2
sont des potentiels pour le grapheG.2 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Chemin optimal
Math ́ematiques
TD n◦ 5(c) `
A partir du potentielπ=πi , trouv ́e `a la question pr ́ec ́edente, on d ́efinit un
nouveau grapheG′ = (A, S, W′ ) dont la valuationW′ est d ́efinie par
∀(x, y)∈A, W′ (x, y) =W(x, y)−M(x, y) =W(x, y) +π(x)−π(y)
repr ́esenter ce graphe (avec les nouveaux poids sur chaque arcs).
(d) Calculer les plus courts chemins du sommet 1 `a tous les autres sommets dugrapheG ′
, en utilisant un algorithme de votre choix (justifier ce choix). Repr ́esenter
l’arbre de parcours correspondant.
Indication :On donnera le tableau des calculs interm ́ediaires
(e) En admettant que l’arbre de parcours des plus courts chemins deGest le mˆeme
que celui deG′ calculer les distances minimales dansGdepuis le sommet 1.
Indication :On pourra se contenter de donner la nouvelle matrice des dis-
tancesDist
2. SoitG= (S, A, W) un graphe orient ́e et valu ́equelconqueetπun potentiel pour
G. On pose :
∀(x, y)∈A, W′ (x, y) =W(x, y) +π(x)−π(y)
(a) Pourquoi trouver un potentiel pour un grapheGsimplifie-t-il le calcul des
distances minimales ?
Indication :Penser au signe des nouvelles valuationsW′ .
(b) SoitC= (x0 , x1 , x2 , . . . , xp , x0 ) un circuitde poids n ́egatifdu grapheG.
Utiliser l’in ́egalit ́e (2) pour minorer la somme des poids du circuitC:W(x 0
, x1 ) +W(x1 , x2 ) +· · ·+W(xp , x0 )≥. . .?
que peut on en d ́eduire pourC?
(c) Supposons qu’on puisse calculer les distances minimalesd(x) du graphesG
depuis un sommetx0 . Montrer quedest un potentiel pour le grapheG.
Indication :Pour un arc(x, y)comparer
la longueur du chemin le plus court dex0 `a
yavec celle du chemin compos ́e du chemin
le plus court dex0 `axpuis de(x, y)x 0x yd(x) d(y)
W(x, y)
(d) En d ́eduire une condition n ́ecessaire et une condition suffisante pour avoir qu’un
graphe orient ́e et valu ́eG= (S, A, W) poss`ede un potentiel.3 philippe.roux@univ-rennes1.fr licence CC-BY-NC-SA
DUT Informatique
semestre 2
Th ́eorie des Graphes
Chemin optimal
Math ́ematiques
TD n◦ 5
Exercice5
Pour chacun des graphes ci-dessous justifier qu’on ne peut utiliserque l’algorithme de
Bellman-Ford pour calculer les chemins de longueur minimale ou maximale `a partir du
sommets= 11 23 45 67 314 718 16−3 111615 100 99 `a partir du sommets= 1 :1 234 56 7−1 201 −110 55 1417 155
`a partir du sommets= 3 :12 34 567 81615 58 04 214 23 013 −15