Théorie des graphes : Td2 chemins optimaux dans les graphes
Télécharger PDFTD 2 : Chemins optimaux dans les graphes
Recherche opérationnelle S3.
2016-2017
Exercice 1
— Table de routage d’un réseau
Dans un réseau à commutation de paquets, une table permet d’indiquer, pour chaque nœud, le canal par lequel un paquet doit être acheminé en fonction de sa destination. Étant donné un réseau, l’objectif est de construire une table de routage optimale.
Soit un réseau de 4 nœuds représenté par un graphe orienté dont la matrice d’adjacence est la suivante :
1 2 3 4
1 : ∞ 3 ∞ 3
2 : 2 ∞ 2 2
3 : 1 ∞ ∞ 4
4 : 4 4 ∞ ∞
1. Rappeler le nom de deux algorithmes utilisés pour calculer le plus court chemin entre le sommet 1 et tous les autres :
- Algorithme de Dijkstra
- Algorithme de Bellman-Ford
2. Pour obtenir les chemins optimaux entre chaque paire de sommets, appliquer l’algorithme de Floyd-Warshall.
L’algorithme de Floyd-Warshall est défini comme suit :
Pour un graphe G = (X, U) avec X = {1, 2, 3, 4}, on initialise les matrices π(0) et P(0) :
π(0)(i,j) = valeur de l’arc (i, j) (∞ si l’arc n’existe pas, 0 si i = j)
P(0)(i,j) = i
Pour m = 1, 2, ..., n, faire :
Pour i = 1, 2, ..., n, faire :
Pour j = 1, 2, ..., n, faire :
Si π(m−1)(i,m) + π(m−1)(m,j) < π(m−1)(i,j), alors :
π(m)(i,j) = π(m−1)(i,m) + π(m−1)(m,j)
P(m)(i,j) = P(m−1)(m,j)
Sinon :
π(m)(i,j) = π(m−1)(i,j)
P(m)(i,j) = P(m−1)(i,j)
3. À partir de la matrice P(n), déduire la table T de routage optimal dans le réseau, c’est-à-dire pour chaque couple (u, v), déterminer le successeur de u dans un plus court chemin de u à v.
Exercice 2
— Conditions d’optimalité
1. Soit G = (X, U) un graphe orienté avec un sommet x et dont les arcs (u, v) ont des valeurs ω(u, v) ∈ ℝ. On associe à chaque sommet u un nombre du.
Démontrer que les nombres du ∈ ℝ représentent les valeurs des chemins de valeur minimale de x à u si et seulement si dx = 0 et dv − du ≤ ω(u, v) pour tout arc (u, v) de U.
2. Résoudre le système suivant en le ramenant à un problème de chemin dans un graphe :
x3 − x4 ≤ 5
x4 − x1 ≤ −10
x1 − x3 ≤ 8
x2 − x1 ≤ −11
x3 − x2 ≤ 2
3. Même question pour le système suivant :
x3 − x2 ≤ 5
x4 − x3 ≤ −2
x4 − x2 ≤ 4
x1 − x2 ≤ 3
x5 − x1 ≤ 2
x3 − x5 ≤ 7
x5 − x4 ≤ −1
Exercice 3
— Coupes disjointes et plus courts chemins
Soit G = (V, A) un graphe orienté sur les arcs. Soient x et y deux nœuds du graphe. Une coupe séparant x et y est un sous-ensemble d’arcs de A tel que leur suppression supprime tous les chemins de x vers y.
1. Montrer que, après suppression d’une coupe C séparant x et y, V est divisé en deux ensembles X et Y = V \ X tels que tout arc de G reliant X à Y appartient à C.
2. Montrer que le nombre maximal de coupes disjointes séparant x et y est égal au nombre d’arcs dans un plus court chemin de x vers y.
Exercice 4
— Conversion de monnaie
Soit G un graphe dont les nœuds représentent une monnaie et chaque arc (u, v), s’il existe, représente une conversion possible de la monnaie u vers la monnaie v. Dans ce cas, l’arc est valué avec le taux de conversion.
Sous quelle condition peut-on devenir infiniment riche ? Transformer ce graphe en un graphe H de sorte que la recherche d’un plus court chemin dans H permet de déterminer si cette possibilité existe. L’algorithme de Dijkstra peut-il être utilisé pour résoudre ce problème ?
FAQ
Qu’est-ce qu’un graphe orienté ?
Un graphe orienté est une structure composée de nœuds (ou sommets) reliés par des arcs (ou arêtes) qui ont une direction. Chaque arc est défini par une paire ordonnée (u, v), où u est le nœud de départ et v le nœud d’arrivée.
Comment interpréter les valeurs dans une matrice d’adjacence ?
Dans une matrice d’adjacence, chaque valeur π(i,j) représente le coût de l’arc allant du nœud i vers le nœud j. Une valeur ∞ indique qu’il n’existe pas d’arc direct entre ces deux nœuds, tandis que 0 signifie que l’arc relie un nœud à lui-même.
Pourquoi l’algorithme de Dijkstra ne convient-il pas toujours pour les chemins optimaux ?
L’algorithme de Dijkstra est efficace pour trouver le plus court chemin dans un graphe pondéré avec des poids positifs. Cependant, il ne peut pas être utilisé pour les graphes contenant des arcs de poids négatif ou des cycles de poids négatif, car il ne garantit pas la convergence dans ces cas.