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.
Soit χ le nombre chromatique du graphe. A-B-C-D est un sous graphe complet d'ordre 4 donc .
La coloration du graphe nécessite au moins quatre couleurs.
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.
Les sommets de la matrice M sont pris dans l'ordre alphabétique, par conséquent, le terme situé à l'intersection de la première ligne et de la huitième colonne de la matrice , donne le nombre de chaînes de longueur 4 partant du sommet A et aboutissant au sommet H.
Il y a 9 chaînes de longueur 4 partant du sommet A et aboutissant au sommet H donc il y a neuf trajets possibles permettant d'aller du dépôt A au point de collecte H en quatre étapes.
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.
graphe nº 1
Pour déterminer le trajet le plus court pour aller de A à H, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 3 (A) | 7 (A) | 11 (A) | ∞ | ∞ | ∞ | ∞ | B (3) | |
| 6(B) | 10 (B) | 14 (B) | ∞ | ∞ | ∞ | C (6) | ||
| 10 (B) | 9 (C) | ∞ | ∞ | ∞ | E (9) | |||
| 10 (B) | 17 (E) | 19 (E) | ∞ | D (10) | ||||
| 17 (E) | 12 (D) | ∞ | G (12) | |||||
| 16 (G) | 24 (G) | F (16) | ||||||
| 23 (F) | H (23) |
Le sommet H étant marqué, pour lire la chaîne de poids minimal, on part de H et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court possible pour aller de A à H est A-B-D-G-F-H. Le temps minimum de parcours est de 23 minutes.
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.
La chaîne 1-2-5-7-8-6-4-3 contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le 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.
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. D'où :
| Sommets | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Degré des sommets du graphe | 2 | 4 | 4 | 2 | 4 | 5 | 2 | 3 |
Le graphe est connexe et contient seulement deux sommets de degré impair donc il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (6 ou 8) et finissant par le deuxième sommet de degré impair.
En entrant dans le lotissement par le sommet 8, il est possible de parcourir le lotissement en empruntant chaque voie une fois et une seule. Par exemple 6-5-8-7-5-2-1-3-2-6-4-3-6-8.
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.