Rallye sportif en VTT

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Graphes et suites numériques
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