Exercices
179
© Dunod – Toute reproduction non autorisée est un délit.
NB : l’arc (B, D) est valué : 22 ; les arcs (A, D) et (B, E) sont valués : 6.
*4.5 algo rithme de ForD : cas d’une maxi mi sa tion
On donne le graphe ci- dessous.
1. Mon trer que G est sans cir cuit : a for tiori, G ne com porte pas de cir
cuit absor bant. Pour cela vous trou ve rez une numé ro ta tion topologique des
som mets (rap pel : dans celle ci, tout arc (x i , x j ) est tel que i , j).
2. Appli quer l’algo rithme de Ford pour déter mi ner les che mins de valeur
maximale, d’ori gine x 1 vers tous les autres som mets (traiter les sommets
dans l’ordre de cette numérotation topologique).
*4.6 algo rithme de Dijkstra
Un livreur de piz zas doit livrer une com mande en moins de 14 minutes. Chaque arête
du graphe repré senté par la figure ci dessous indique la durée, expri mée en minutes,
des tra jets entre les dif fé rents car re fours de son arron dis se ment. La société fabri quant
les pizze se situe au som met A du graphe et la livrai son doit s’effec tuer au som met H.
1. Dire pour quelles rai sons le livreur peut résoudre ce pro blème en uti li sant
l’algo rithme de Dijkstra ; au préa lable chaque arête [x,y] sera rem pla cée par
deux arcs de sens opposés : (x,y) et (y,x) ; sauf pour celles issues de A et de H.
2. Le livreur arrivera til à temps ?
179
© Dunod – Toute reproduction non autorisée est un délit.
NB : l’arc (B, D) est valué : 22 ; les arcs (A, D) et (B, E) sont valués : 6.
*4.5 algo rithme de ForD : cas d’une maxi mi sa tion
On donne le graphe ci- dessous.
1. Mon trer que G est sans cir cuit : a for tiori, G ne com porte pas de cir
cuit absor bant. Pour cela vous trou ve rez une numé ro ta tion topologique des
som mets (rap pel : dans celle ci, tout arc (x i , x j ) est tel que i , j).
2. Appli quer l’algo rithme de Ford pour déter mi ner les che mins de valeur
maximale, d’ori gine x 1 vers tous les autres som mets (traiter les sommets
dans l’ordre de cette numérotation topologique).
*4.6 algo rithme de Dijkstra
Un livreur de piz zas doit livrer une com mande en moins de 14 minutes. Chaque arête
du graphe repré senté par la figure ci dessous indique la durée, expri mée en minutes,
des tra jets entre les dif fé rents car re fours de son arron dis se ment. La société fabri quant
les pizze se situe au som met A du graphe et la livrai son doit s’effec tuer au som met H.
1. Dire pour quelles rai sons le livreur peut résoudre ce pro blème en uti li sant
l’algo rithme de Dijkstra ; au préa lable chaque arête [x,y] sera rem pla cée par
deux arcs de sens opposés : (x,y) et (y,x) ; sauf pour celles issues de A et de H.
2. Le livreur arrivera til à temps ?