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, on peut disposer d’une table qui indique, en chaque
noeud, le canal vers lequel un paquet qui arrive doit être acheminé, connaissant la destination
de ce paquet. Etant donné un réseau, on va s’intéresser à l’élaboration d’une table des routages
optimaux.
Soit le réseau de 4 noeuds décrit par un graphe orienté dont la matrice d’adjacence est la
suivante :
1 2 3 4
1- 3 - 3
22 - 2 2
31 - - 14 - 4 4 -
1. Rappeler le nom de deux algorihtmes que l’on peut utiliser pour calculer le plus court chemin
du sommet1vers tous les autres.
2. En fait on a besoin d’avoir les chemins optimaux entre chaque paire de sommets. Appliquer
l’algorithme de Floyd-Warshall pour ce faire. Expliciter les matricesπetPà chaque étape
de l’algorithme.
3. Déduire dePla tableTde routage optimal dans le réseau. C’est à dire, pour tout couple
(u,v)le successeur deudans un plus court chemin deuàv.
Algorithme 1Floyd-warshall (G= (X,U))π (0)ij :=valeur de l’arc(i,j)
// si l’arc(i,j)n’existe pas on met+∞, et sii=jon met 0P (0)
(i,j) :=i//à la fin de l’algorithmeP( n)(i,j)contient le prédecesseur dejdans un chemin
optimal deiversj
Pourm= 1,2,...,nFaire
Pouri= 1,2,...,nFaire
Pourj= 1,2,...,nFaire
// Est-il plus court d’aller deiàjen passant parm?Si(π (m−1)im +π(m−1) mj
< π(m−1) ij)Alors π(m) ij:=π (m−1)im +π(m−1) mjP (m)ij :=P(m−1) mjSinon π(m) ij:=π (m−1)ij P(m) ij:=P (m−1)ij 1
Exercice 2—Conditions d’optimalité
1. SoitG= (X,U)un graphe orienté avec un sommetset dont les arcs(u,v)ont des valeurs
ω(u,v)∈R. On associe chaque sommetuà un nombredu . Démontrer le théorème suivant :
Les nombresdu ∈Rreprésentent les valeurs des chemins de valeur minimale desàxu si et
seulement sids = 0etdv −du ≤ω(u,v)pour tout arc(u,v)deU.
2. Résoudre le système suivant en le ramenant à un problème de chemin dans un graphe :x 3−x 4≤5 x4 −x1 ≤−10x 1−x 3≤8 x2 −x1 ≤−11x 3−x 2≤2 3. Même question pour le système :x 3−x 2≤5 x4 −x3 ≤−2x 4−x 2≤4 x1 −x2 ≤3x 5−x 1≤2 x3 −x5 ≤7x 5−x 4≤−1
Exercice 3—Coupes disjointes et plus court chemins
SoitG= (V,A)un graphe orienté sur les arcs. Soientxetydeux nœuds du graphe. On appelle
une coupe séparantxetyun sous-ensemble d’arcs deAtel que retirer ces arcs deGsupprime
tout chemin dexversy.
1. Montrer que, après suppression d’une coupeCséparantxety,Vest coupé en deux ensembles
XetY=V\Xtels que tout arc deGreliantXàYappartient àC.
2. Montrer que le nombre maximum de coupes disjointes séparantxetyest égal au nombre
d’arcs dans un plus court chemin dexversy.
Exercice 4—Conversion de monnaie
SoitGun graphe dont les nœuds représentent une monnaie et chaque arc(u,v), s’il existe,
représente une conversion possible d’une monnaieuvers une monnaiev. Dans ce cas l’arc est valué
avec le taux de la conversion.
Sous quelle condition peut-on devenir infiniment riche ? Transformer ce graphe en un grapheH
de sorte que chercher un plus court chemin dansHpermette de savoir s’il est possible de devenir
infiniment riche. L’algorithme de Dijkstra peut-il nous aider ?