"'O
Chapitre 6 • Graphes et ordonnancement
c) La dernière ligne de la matrice M5 est : 1 2 1 1 0 1.
Le seul chemin de longueur 5 entre F et A est FADCBA, il ne passe pas par E.
Deux chemins de longueur 5 existent entre F et B : FADFEB et FADCEB . Ce
deuxième chemin passe par toutes les salles : c'est un chemin hamiltonien.
Le seul chemin de longueur 5 qui va de F à C est FEBADC et il passe par toutes les
salles.
FADFAD est le seul chemin reliant F à D, il ne passe pas par B, C et E.
Enfin, FEBADF relie F à lui-même sans passer par C.
Finalement, il y a deux chemins de longueur 5 qui visitent toutes les salles.
d) Le calcul de M6 montre qu' il n'y a qu' un seul circuit de longueur 6 qui relie F à
lui-même. Ce circuit est FADFADF, il ne passe pas par toutes les salles.
Partie C
a)
20
B ~~--~-.-----....-~~~......-~~ F
20
E
Figure 6.17
g
b) Le calcul de M8 permet de dire qu'il y a trois circuits de longueur 8 de F à F. Ces
:J
o
trois circuits sont :
LI)
~
• FADCEBADF qui consomme 25 + 30 + 40 + 25 + 20 + 25 + 30 + 20 = 215 points.
N
@
• FEBADFADF et FADFEBADF qui consomment 195 points.
166
Exercices corrigés
m Pour chacun des graphes (fig. 6.18), faire le tableau des successeurs et des
prédécesseurs.