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 № 1.
Le dépôt est représenté par le sommet A et les autres sommets représentent les différents points de collecte.
graphe nº 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.
On appelle M la matrice associée au graphe № 1, M étant construite en utilisant les sommets dans l'ordre alphabétique. On donne ci-dessous la matrice : 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.
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.
Pour déterminer le trajet le plus court pour aller de A à H, on utilise l'algorithme de Dijkstra.
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.
Justifier que ce graphe est connexe.
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
Parcourir le lotissement en empruntant chaque voie une fois et une seule c'est chercher si le graphe contient une chaîne eulérienne.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.