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
&nbsp
Trajets d&rsquo un camion de recyclage

Graphes

Corrig&eacute

44

Ens. de sp&eacute cialit&eacute

matT_1200_14_06C

D&rsquo apr&egrave s Pondich&eacute ry &bull Avril 2012

Exercice 2 &bull 5 points

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

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

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


&gt 1.  Afin de rendre son plan plus lisible, le chauffeur du camion souhaite colorer les sommets du graphe repr&eacute sentant son r&eacute seau de mani&egrave re &agrave ce que deux sommets adjacents n&rsquo aient jamais la m&ecirc me couleur. Peut-il utiliser seulement trois couleurs ? Justifier. (1 point)

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

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

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

&gt 4.  Le point de collecte H est lui-m&ecirc me un lotissement r&eacute sidentiel priv&eacute dont un plan est repr&eacute sent&eacute &agrave l&rsquo aide du graphe (non pond&eacute r&eacute ) ci-dessous. Les sommets sont les diff&eacute rents carrefours et les ar&ecirc 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&eacute 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&eacute e conseill&eacute e  : 45 min.

Les th&egrave mes en jeu

Matrice associ&eacute e &agrave un graphe &bull Graphes pond&eacute r&eacute s &bull Cha&icirc nes de longueur donn&eacute e.

Les conseils du correcteur

&gt     1.  Consid&eacute rez par exemple les sommets A, B, C et D.

&gt     2.  Le nombre de trajets en 4 &eacute tapes d&rsquo un sommet &agrave un autre est l&rsquo un des coefficients de la matrice M4.

&gt     3.  On peut utiliser un algorithme, par exemple l&rsquo algorithme de Dijkstra.

&gt     4.  b)  D&eacute terminez si le graphe est eul&eacute rien  il suffit pour cela d&rsquo examiner le degr&eacute de chaque sommet.