Parcours dans les salles d’une MJC

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2014 | Académie : Moyen-Orient
Corpus Corpus 1
Parcours dans les salles d’une MJC

Graphes, « plus court chemin »

matT_1405_09_09C

Ens. de spécialité

34

CORRIGE

Liban • Mai 2014

Exercice 3 • 5 points

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. (0,75 point)

>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. (1 point)

>3. On range les sommets par ordre alphabétique.

Donner la matrice d’adjacence associée au graphe. (1 point)

>4. On donne :

.

En déduire le nombre de chemins de longueur 4 entre les sommets B et H. (0,75 point)

>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é.


 

À l’aide d’un algorithme, déterminer le temps minimal en minutes pour aller de B à H. (1,5 point)

Les clés du sujet

Les thèmes en jeu

Matrice • Graphe pondéré • Chaîne eulérienne • Plus court chemin.

Les conseils du correcteur

>2. Utilisez le théorème d’Euler pour déterminer si le graphe possède une chaîne eulérienne.

>3. Les coefficients de la matrice d’adjacence associée à un graphe sont égaux à 0 ou 1.

>4. Chaque coefficient de la matrice est égal au nombre de chemins de longueur 4 entre deux sommets donnés.

>5. Utilisez l’algorithme de Dijkstra.

Corrigé
Corrigé

>1. Déterminer si un graphe est connexe

Deux sommets quelconques sont reliés par une chaîne. On peut passer d’une salle quelconque à une autre par un passage ou une suite de passages.

Donc le graphe est connexe.

>2. Déterminer si un graphe possède une chaîne eulérienne

Notez bien

Une chaîne eulérienne peut passer plusieurs fois par le même sommet.

Une chaîne eulérienne d’un graphe est une chaîne contenant une fois et une seule chaque arête du graphe, c’est-à-dire ici un chemin utilisant une fois et une seule chaque passage.

Info

Le degré d’un sommet est le nombre d’arêtes dont une extrémité est ce sommet.

D’après le théorème d’Euler, un graphe connexe possède une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2.

On peut résumer dans un tableau les degrés des différents sommets du graphe :

 

Sommet

A

B

C

D

E

F

H

Degré

4

2

4

3

4

3

2

 

Notez bien

Les extrémités de cette chaîne sont nécessairement les deux sommets de degré impair.

Le graphe a deux sommets de degré impair, D et F.

D’après le théorème d’Euler, ce graphe possède une chaîne eulérienne ; un exemple de telle chaîne est D – C – B – A – C – E – A – F – E – D – H – F.

L’agent de service peut donc passer par toutes les salles en utilisant une fois et une seule chaque passage.

>3. Donner la matrice d’adjacence associée à un graphe

Notez bien

Le coefficient situé à l’intersection de la ligne et la colonne de est égal à 0 s’il n’y a pas d’arête d’extrémités les sommets et , à 1 s’il y en a une.

La matrice d’adjacence associée au graphe est :

>4. Déterminer le nombre de chemins de longueur donnée entre deux sommets d’un graphe

Les sommets sont rangés par ordre alphabétique. Le sommet B est le sommet numéro 2, le sommet H a le numéro 7.

Le nombre de chemins de longueur 4 entre les sommets B et H est le coefficient de situé à l’intersection de la ligne 2 et de la colonne 7 (ou de la ligne 7 et de la colonne 2), c’est-à-dire 6.

Il existe six chemins de longueur 4 entre les sommets B et H.

>5. Déterminer un « plus court chemin » sur un graphe

Pour trouver un chemin le plus rapide du sommet B au sommet H et le temps correspondant, on utilise l’algorithme de Dijkstra, qui peut se résumer par le tableau ci-dessous :

 

A

B

C

D

E

F

H

2 (B)

0

2 (B)

2 (B)

4 (A)

5 (A)

3 (C)

3 (C)

5 (A)

3 (C)

5 (A)

5 (D)

4 (E)

5 (D)

5 (D)

 

Notez bien

En complétant la dernière case en bas à droite par 5 (F), on obtient un autre chemin « de longueur minimale » : B – C – E – F – H, qui comporte une étape de plus que le précédent, mais correspond également à une durée de 5 minutes.

Un chemin le plus rapide du sommet B au sommet H est donc :

La durée correspondante, c’est-à-dire le temps minimal de B à H, est 5 minutes.