Trajets d’un camion de recyclage

Merci !

Annales corrigées
Classe(s) : Tle L - Tle ES | Thème(s) : Suites
Type : Exercice | Année : 2012 | Académie : Sujet zéro
Unit 1 - | Corpus Sujets - 1 Sujet
 
Trajets d’un camion de recyclage

Graphes

Corrigé

44

Ens. de spécialité

matT_1200_14_06C

D’après Pondichéry • Avril 2012

Exercice 2 • 5 points

Certaines questions ont été modifiées ou remplacées pour adapter le sujet au nouveau programme.

Les points de collecte d’un camion d’une société recyclant des «  déchets papier  », ainsi que les temps de trajet (en minutes) entre ces différents points, sont représentés par le graphe n&deg 1.

Le dépôt est représenté par le sommet A et les autres sommets représentent les différents points de collecte.


>1.  Afin de rendre son plan plus lisible, le chauffeur du camion souhaite colorer les sommets du graphe représentant son réseau de manière à ce que deux sommets adjacents n’aient jamais la même couleur. Peut-il utiliser seulement trois couleurs ? Justifier. (1 point)

>2.  On appelle M la matrice associée au graphe n&deg 1, M étant construite en utilisant les sommets dans l’ordre alphabétique. On donne ci-après la matrice M4  :

Combien y a-t-il de trajets possibles permettant d’aller du dépôt A au point de collecte H en quatre étapes  ? Justifier la réponse. (1 point)

>3.  Le conducteur doit se rendre du dépôt A au point de collecte H. Il cherche le chemin qui minimise le temps de trajet. Déterminer ce chemin en expliquant le procédé utilisé, et préciser le temps minimum de parcours obtenu. (1,5 point)

>4.  Le point de collecte H est lui-même un lotissement résidentiel privé dont un plan est représenté à l’aide du graphe (non pondéré) ci-dessous. Les sommets sont les différents carrefours et les arêtes sont les voies de circulation.


a)  Justifier que ce graphe est connexe. (0,5 point)

b)  Le conducteur du camion doit passer le long de chaque voie afin de collecter les déchets individuels de chaque habitation. Il entre dans le lotissement par le sommet 8 : lui est-il possible de parcourir le lotissement en empruntant chaque voie une fois et une seule ? Justifier. (1  point)

Durée conseillée  : 45 min.

Les thèmes en jeu

Matrice associée à un graphe • Graphes pondérés • Chaînes de longueur donnée.

Les conseils du correcteur

>    1.  Considérez par exemple les sommets A, B, C et D.

>    2.  Le nombre de trajets en 4 étapes d’un sommet à un autre est l’un des coefficients de la matrice M4.

>    3.  On peut utiliser un algorithme, par exemple l’algorithme de Dijkstra.

>    4.  b)  Déterminez si le graphe est eulérien  il suffit pour cela d’examiner le degré de chaque sommet.