Chapitre 6 • Graphes et ordonnancement
Partie B
a) Calculer M 3 . Expliquer la signification des nombres de la dernière ligne de cette
matrice.
b) Le joueur se trouvant dans la salle F, déterminer les salles dans lesquelles il peut
se retrouver en quatre déplacements. Écrire tous les déplacements correspondants.
c) Est-il possible, à partir de F et en cinq déplacements, de visiter chaque salle?
d) Le joueur pourra-t-il de partir de F et y revenir en exactement six déplacements ?
Si oui, ces trajets permettent-ils de visiter chaque salle ?
Partie C
Chaque entrée dans une salle coûte au joueur un certain nombre de points. Les
entrées dans les salles A, B, C, D, E et F coûtent respectivement 25, 20, 40, 30, 25 et
20 points. Le développeur souhaite que le joueur ne puisse pas faire plus de huit
déplacements à l'intérieur du donjon, à partir de son entrée en F et son retour en F.
a) Dessiner le graphe valué modélisant la consommation en points de chaque déplacement.
b) Combien de trajets de huit déplacements le joueur peut-il faire à l'intérieur du
donjon?
c) En effectuant ces huit déplacements, combien de points le joueur consommera-til au maximum ?
Solution du TD
Partie A
~
a) Voir le graphe de la fig. 6.16.
c
:J
0
LI)
..--t
0
N
@
.......
..c
O'l
·;::::
>Q.
0
u
E
Figure 6.16
164