Rallye sportif en VTT

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2012 | Académie : Asie
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Rallye sportif en VTT
 
 

Graphes

Corrigé

42

Ens. de spécialité

matT_1206_05_00C

 

Asie • Juin 2012

Exercice 2 • 5 points

Une association organise un rallye sportif en VTT : six zones de regroupement sont déterminées et sont reliées par des chemins.

Ce parcours est modélisé par le graphe ci-dessous, où les sommets de A à F représentent les zones de regroupement, et les arêtes les chemins.

Les arêtes sont pondérées par les distances, exprimées en kilomètres, nécessaires pour parcourir ces chemins.

Les candidats sont positionnés initialement sur la zone A et doivent, après avoir parcouru tous les chemins, revenir à la zone initiale.

Chaque fois qu’un candidat emprunte pour la première fois un chemin il doit déposer, à un endroit précis, un jeton personnalisé, attestant son passage.


 

>1. Quel nombre minimal de jetons est-il nécessaire de donner à chaque candidat ?

>2. Un candidat souhaite faire le parcours, en empruntant tous les chemins une fois et une seule. Est-ce possible ? Justifier la réponse.

>3. Soit M la matrice associée au graphe G (on ordonne les sommets dans l’ordre alphabétique).

a) Écrire la matrice M.

b) On donne les matrices :

et

Un candidat est actuellement au point de rendez-vous D et on lui signale qu’il a oublié son dossard au point B. Devant le récupérer, il souhaite emprunter au maximum trois chemins. Combien a-t-il de possibilités ?

c) Donner le trajet correspondant à la distance la plus courte lui permettant d’aller récupérer son dossard.

Durée conseillée : 40 min.

Les thèmes en jeu

Graphes pondérés • Matrice associée à un graphe • Chaîne eulérienne.

Les conseils du correcteur

>1. Comptez le nombre d’arêtes du graphe.

>2.b) Cherchez les trajets du point D au point B comportant au maximum trois chemins, c’est-à-dire en comportant deux ou trois (il n’existe aucune arête d’extrémités B et D, c’est-à-dire aucun trajet d’un seul chemin de D à B).

Les coefficients de la matrice indiquent le nombre de chaînes de longueur 2 entre deux sommets donnés ; les coefficients de la matrice indiquent le nombre de chaînes de longueur 3 entre deux sommets donnés.

Corrigé

>1. Compter le nombre d’arêtes d’un graphe

Le graphe comporte 9 arêtes ; il existe donc au total 9 chemins.

Chaque candidat doit donc avoir au minimum 9 jetons.

>2. Déterminer si un graphe est eulérien

 

Notez bien

Un graphe eulérien est un graphe admettant un cycle eulérien, c’est-à-dire une chaîne fermée (le sommet de départ et le sommet d’arrivée sont confondus) comportant une fois et une seule chacune des arêtes du graphe.

La question posée est équivalente à la question suivante « le graphe donné est-il un graphe eulérien ? ».

D’après un théorème du cours « un graphe simple non orienté connexe est un graphe eulérien si et seulement si chaque sommet est de degré pair ».

Le graphe donné est simple, non orienté, connexe (il existe au moins une chaîne entre deux sommets distincts donnés) ; on détermine le degré de chaque sommet, c’est-à-dire le nombre d’arêtes dont l’une des extrémités est le sommet considéré.

On résume les résultats dans un tableau :

 

Sommet

A

B

C

D

E

F

Degré

4

2

4

2

2

4

 

Les sommets sont tous de degré pair, donc le graphe est eulérien.

Il est donc possible de faire le parcours en empruntant une fois et une seule tous les chemins.

>3.a) Déterminer la matrice associée à un graphe

 

Info

Si on note le coefficient de la e ligne et la e colonne de la matrice  : s’il existe un chemin du sommet i au sommet j et s’il n’existe aucun chemin du sommet i au sommet j.

Soit M la matrice associée au graphe G :

b) Utiliser les puissances d’une matrice pour déterminer un trajet correspondant à une distance minimale

 

Info

Si est un entier naturel non nul et si est le coefficient de la e ligne et la e colonne de la matrice , alors est le nombre de chaînes de longueur et d’extrémités les sommets i et j.

On cherche les chaînes de longueur 2 ou 3 et d’extrémités D et B.

Le coefficient correspondant (ligne 4, colonne 2) de la matrice est 1 : il existe une seule chaîne de longueur 2 de D à B.

Le coefficient correspondant de la matrice est 3 : il existe trois chaînes de longueur 3 de D à B.

Le candidat qui souhaite emprunter au maximum trois chemins pour aller de D à B a donc au total quatre possibilités : un trajet comportant deux chemins (D-F-B) et trois trajets comportant trois chemins (D-C-A-B ; D-F-A-B ; D-C-F-B).

c) Déterminer le trajet correspondant à la distance la plus courte

 

Notez bien

Pour calculer la longueur d’un trajet, on additionne les « poids » portés par les arêtes (chemins) formant ce trajet.

La longueur du trajet D-C-A-B est 10 km.

Les longueurs des trajets D-F-A-B et D-C-F-B est 14 km.

La longueur du trajet D-F-B est 14 km.

Le trajet correspondant à la distance la plus courte est donc D-C-A-B.