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

Corrigé

>1. Déterminer s’il est possible de colorier un graphe avec un nombre donné de couleurs

Puisque les quatre sommets A, B, C et D sont deux à deux reliés, il faut au moins quatre couleurs pour colorer les sommets du graphe de manière à ce que deux sommets adjacents n’aient jamais la même couleur.

Il est donc impossible d’utiliser seulement trois couleurs.

>2. Déterminer sur un graphe le nombre de trajets comportant un nombre donné d’étapes pour aller d’un point à un autre

Le nombre de trajets permettant d’aller du point A au point H en quatre étapes est le coefficient situé à l’intersection de la première ligne et de la huitième colonne de la matrice M4.

Ce coefficient est égal à 9.

Il existe donc 9 trajets conduisant en quatre étapes du point A au point H.

>3. Rechercher sur un graphe pondéré un chemin de longueur ­minimale

Pour déterminer un chemin qui minimise le temps de trajet de A à H, on utilise l’algorithme de Dijkstra :


A


B


C


D


E


F


G


H



0









A


0 (A)


3 (A)


7 (A)


11 (A)






B



3 (A)


6 (B)


10 (B)


14 (B)





C





10 (B)


9 (C)





E





10(B)



17 (E)


19 (E)



D





10(B)



17 (E)


12(D)



G







16 (G)


12 (D)


24 (G)


F







16 (G)



23(F)


H









23(F)