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 M⁴ :

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)