Une association organise un rallye sportif en VTT : six zones de regroupement sont déterminées et sont reliées par des chemins.
Ce parcours est modélisé par le graphe ci-dessous, où les sommets de A à F représentent les zones de regroupement, et les arêtes les chemins.
Les arêtes sont pondérées par les distances, exprimées en kilomètres, nécessaires pour parcourir ces chemins.
Les candidats sont positionnés initialement sur la zone A et doivent, après avoir parcouru tous les chemins, revenir à la zone initiale.
Chaque fois qu'un candidat emprunte pour la première fois un chemin il doit déposer, à un endroit précis, un jeton personnalisé, attestant son passage.
Quel nombre minimal de jetons est-il nécessaire de donner à chaque candidat ?
Chaque fois qu'un candidat emprunte pour la première fois un chemin il doit déposer un jeton donc le nombre de jetons nécessaire est égal au nombre d'arêtes du graphe G.
| Sommets | A | B | C | D | E | F |
| Degré des sommets | 4 | 2 | 4 | 2 | 2 | 4 |
Le nombre n d'arêtes du graphe est égal à la demi-somme des degrés des sommets d'où
Il faudra donner 9 jetons à chaque candidat.
Un candidat souhaite faire le parcours, en empruntant tous les chemins une fois et une seule. Est-ce possible ? Justifier la réponse.
La chaîne A-B-F-D-C-E contient tous les sommets du graphe donc le graphe est connexe.
Le graphe G est connexe et tous ses sommets sont de degré pair alors il existe un cycle eulérien.
Il est possible pour un candidat en partant de la zone A de faire le parcours, en empruntant tous les chemins une fois et une seule pour revenir à la zone A.
Soit M la matrice associée au graphe G ( on ordonne les sommets dans l'ordre alphabétique).
Écrire la matrice M.
La matrice d'adjacence du graphe est
On donne les matrices et
Un candidat est actuellement au point de rendez-vous D et on lui signale qu'il a oublié son dossard au point B. Devant le récupérer, il souhaite emprunter au maximum trois chemins.
Combien a-t-il de possibilités ?
Le terme de la matrice situé à l'intersection de la quatrième ligne et de la deuxième colonne est égal à 1 donc il y a une seule chaîne de longueur 2 reliant le sommet D au sommet B
Le terme de la matrice situé à l'intersection de la quatrième ligne et de la deuxième colonne est égal à 3 donc il y a trois chaînes de longueur 3 reliant le sommet D au sommet B.
Il y a 4 possibilités en partant du point D de rejoindre le point B en empruntant au maximum trois chemins.
Donner, le trajet correspondant à la distance la plus courte lui permettant d'aller récupérer son dossard.
Pour déterminer le trajet le plus court pour aller de D à B, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | Sommet sélectionné |
| ∞ | ∞ | ∞ | 0 | ∞ | ∞ | D (0) |
| ∞ | ∞ | 2 (D) | ∞ | 6 (D) | C (2) | |
| 8 (C) | ∞ | 6 (C) | 4 (C) | F (4) | ||
| 8 (C) | 14 (F) | 6 (C) | E (6) | |||
| 8 (C) | 14 (F) | A (8) | ||||
| 10 (A) | B (10) |
Le sommet B étant marqué, pour lire la chaîne de poids minimal, on part de B et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court possible pour aller de D à B est D-C-A-B. La distance parcourue est de 10 km.
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.