Théorie des graphes : Correction td 5 graphe s1 s5
Télécharger PDFTD n°5 – Théorie des Graphes : Chemins optimaux
Exercice 1 : Algorithme de Dijkstra
Appliquer l’algorithme de Dijkstra aux graphes suivants pour calculer les chemins de poids minimum depuis le sommet 1.
Graphes donnés :
1 2 3 4 5 6
2 1 4 6
4 2 10
3 1 5 4
4 1 2 3
6 7
4 5 10
1 4 2 10
1 3
2 10
4 5
Exercice 2 : Algorithme de Bellman simplifié
Décomposer les graphes suivants en niveaux, puis appliquer l’algorithme de Bellman simplifié pour calculer les chemins de poids minimum et maximum depuis le sommet 5.
Graphes donnés :
1 2 3 4
5 6 7 8
2 4 1 −1 −3
7 3 2 2 −10
1 2 3 4 5 6 7 8
5 8 2 5 10 −1
1 4 9 4 6 6 4 11
Exercice 3 : Algorithme de Bellman-Ford
Appliquer l’algorithme de Bellman-Ford pour calculer les distances minimales depuis le sommet colorié.
Graphes donnés :
1 2 3 4 5 6
4 3 3 0 1 4
7 2 1 −1 2 12
3 4 5 6 7 8
4 2 3 2 1 3
1 7 2 1 −1 2 12
3 1 2 2 3 0 13 −1 5
Exercice 4 : Potentiel et distances minimales
1. Soit G = (S, A, W) un graphe orienté valué (les poids des arcs sont représentés par une matrice carrée W).
On appelle matrice des poids d’une application π de S dans ℝ, la matrice M définie par :
∀(x, y) ∈ A, M(x, y) = π(y) − π(x).
On dira alors que π est un potentiel de G si :
∀(x, y) ∈ A, W(x, y) ≥ M(x, y).
(a) Calculer les matrices des poids W pour le graphe G et M₂ pour π₂.
Graphe G :
1 2 3 4 5
1 7 −5
2 −2 −4
π₁(1) = 13, π₁(2) = −2, π₁(3) = 0, π₁(4) = 5, π₁(5) = −1.
π₂(1) = 2, π₂(2) = 1, π₂(3) = 2, π₂(4) = 3, π₂(5) = 0.
(b) Comparer W aux matrices M₁ et M₂ pour déterminer si π₁ et π₂ sont des potentiels pour le graphe G.
(c) À partir du potentiel π = πᵢ trouvé à la question précédente, on définit un nouveau graphe G′ = (A, S, W′) dont la valuation W′ est donnée par :
∀(x, y) ∈ A, W′(x, y) = W(x, y) − M(x, y) = W(x, y) + π(x) − π(y).
Représenter ce graphe avec les nouveaux poids sur chaque arc.
(d) Calculer les plus courts chemins du sommet 1 à tous les autres sommets du graphe G′, en utilisant un algorithme de votre choix (justifier ce choix). Représenter l’arbre de parcours correspondant.
(e) En admettant que l’arbre de parcours des plus courts chemins de G est le même que celui de G′, calculer les distances minimales dans G depuis le sommet 1.
2. Soit G = (S, A, W) un graphe orienté et valué quelconque et π un potentiel pour G.
On pose :
∀(x, y) ∈ A, W′(x, y) = W(x, y) + π(x) − π(y).
(a) Pourquoi trouver un potentiel pour un graphe G simplifie-t-il le calcul des distances minimales ?
(b) Soit C = (x₀, x₁, x₂, ..., xₚ, x₀) un circuit de poids négatif du graphe G.
Utiliser l’inégalité (2) pour minorer la somme des poids du circuit C : W(x₀, x₁) + W(x₁, x₂) + ... + W(xₚ, x₀) ≥ ... ?
Que peut-on en déduire pour C ?
(c) Supposons qu’on puisse calculer les distances minimales d(x) du graphe G depuis un sommet x₀.
Montrer que d est un potentiel pour le graphe G.
Indication : Pour un arc (x, y), comparer la longueur du chemin le plus court de x₀ à y avec celle du chemin composé du chemin le plus court de x₀ à x puis de (x, y).
(d) En déduire une condition nécessaire et une condition suffisante pour qu’un graphe orienté et valué G = (S, A, W) possède un potentiel.
Exercice 5 : Bellman-Ford pour chemins négatifs
Pour chacun des graphes ci-dessous, justifier qu’on ne peut utiliser que l’algorithme de Bellman-Ford pour calculer les chemins de longueur minimale ou maximale à partir du sommet indiqué.
Graphes donnés :
Depuis le sommet 1 :
1 2 3 4 5 6 7
3 1 4 7 1 8
1 6 −3
1 1 6 1 5 100 99
Depuis le sommet 1 :
1 2 3 4 5 6
2 0 1 −1 −10
5 5 1 4 17
Depuis le sommet 3 :
1 2 3 4 5 6 7 8
5 8 0 4 2 14
2 3 0 13 −1 5
FAQ
1. Qu’est-ce qu’un potentiel dans un graphe orienté et valué ?
Un potentiel π est une fonction qui associe à chaque sommet x un nombre réel π(x) telle que pour tout arc (x, y), le poids W(x, y) soit supérieur ou égal à π(y) − π(x). Cela permet de simplifier les calculs de distances minimales.
2. Pourquoi l’algorithme de Dijkstra ne fonctionne-t-il pas sur certains graphes ?
L’algorithme de Dijkstra ne fonctionne pas sur les graphes contenant des circuits de poids négatif, car il suppose que les poids sont positifs pour garantir la convergence.
3. Comment justifier l’utilisation de Bellman-Ford plutôt que Dijkstra ?
Bellman-Ford est utilisé lorsque le graphe contient des poids négatifs ou des circuits de poids négatif, car il peut détecter ces cas et fournir les distances correctes malgré leur présence.