Sujet et corrigé de l'exercice de spécialité du bac ES de maths de mai 2014 au Liban
Cacher les corrigés
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.
1. Préciser si ce graphe est connexe en justifiant la réponse.
Si on prend deux sommets quelconques du graphe on peut toujours trouver une chaîne qui les relie, donc le graphe est connexe.
2. Déterminer, en justifiant, si l'agent de service peut passer par toutes les salles en utilisant une fois et une seule chaque passage.
Pour répondre à cette question il s'agit de voir si le graphe admet une chaîne eulérienne. Pour cela on regarde les degrés des sommets :
| Sommet | A | B | C | D | E | F | H |
| Degré | 4 | 2 | 4 | 3 | 4 | 3 | 2 |
Du coup ce graphe connexe possède exactement deux sommets de degré impair, donc il existe une chaîne eulérienne entre les sommets F et D.
L'agent peut réaliser sa mission en utilisant une fois et une seule chaque passage.
3. On range les sommets par ordre alphabétique.
Donner la matrice d'adjacence M associée au graphe.
4. On donne :
En déduire le nombre de chemins de longueur 4 entre les sommets B et H.
On regarde la valeur sur la deuxième ligne (B), la valeur dans la dernière colonne (H), donc il y a 6 chemins de longueur 4 entre B et H.
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é.
A l'aide d'un algorithme, déterminer le temps minimal en minute pour aller de B à H.
On utilise l'algorithme de Dijkstra dont on présente les étapes dans le tableau suivant :
| Départ : B | A | C | D | E | F | Arrivée : H |
| 0 | 2,B | 2,B | ||||
| / | 6,A | 4,A | 5,A | |||
| / | / | 3,C | 3,C | 5,A | ||
| / | / | / | 4,D | 5,A | 5,D | |
| / | / | / | / | 4,E | 5,D | |
| / | / | / | / | / | 5,D,F |
Donc le temps minimal est de 5 minutes et il peut être réalisé de deux façons différentes :
B,C,E,F,H
B,C,D,H
