Les points de collecte d&rsquo un camion d&rsquo 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&rsquo 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&rsquo ordre alphabé tique. On donne ci-aprè s la matrice M4 :
Combien y a-t-il de trajets possibles permettant d&rsquo 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&rsquo 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)
Certaines questions ont é té modifié es ou remplacé es pour adapter le sujet au nouveau programme.