INFO EXERCICE DE BAC ES spé maths. mai 2014 Liban
On a schématisé ci-dessous le plan d'une MJC ( Maison de la jeunesse et de la culture )
par un graphe dont les sommets sont les salles
et les arêtes sont les passages( portes, couloirs ou escaliers) entre les salles.
On appelle H le hall d'entrée et B le bureau du directeur.
En fin de journée un agent de service fait le tour de la MJC pour récupérer dans chaque salle
( bureau du directeur et hall inclus ) les objets oubliés par les enfants.
QUESTION 1.
Préciser si le graphe est connexe en justifiant la réponse.
OUI.
En effet , deux sommets quelconques sont reliés par au moins un chemin.
QUESTION 2.
Déterminer, en justifiant, si l'agent de service peut passer par toutes les salles
en utilisant une fois une seule chaque passage.
OUI.
Il y a en effet ici un graphe non orienté connexe ( simple ) qui
possède exactement deux sommets de degrés impairs ( 3 ).
Ces deux sommets sont F et D.
Il existe donc au moins une chaîne eulérienne reliant les sommets F et D.
QUESTION 3.
On range les sommets par ordre alphabétique.
donner la matrice d'adjacence M associée au graphe.
QUESTION 4.
On donne:
En déduire le nombre de chemins de longueur 4 entre les sommets B et H.
6 se trouve à l'intersection de la seconde ligne et de la 7 ième colonne de M4 .
Donc:
Conclusion: il y a 6 chemins de longueur 4 qui relient B et H
QUESTION 5.
On a indiqué sur le graphe ci-dessous le temps en minutes mis pour passer entre les différentes salles
en ouvrant et fermant les portes à clé.
Déterminer à l'aide d'un algorithme le temps minimal pour aller de B à H.
Faisons le tableau de Moore-Dijkstra.
H ← F( 5 ) ← E( 4 ) ← C( 3 ) ← B(2 ) ← B
Conclusion : Le chemin le plus court est :
BCEFH
Ce n'était pas le seul chemin possible car on a fait un choix.
-------------------------------------------------------------------------------------------------------------------------------------------