Matrices et graphes • Plus court chemin
Corrigé
37
Ens. de Spécialité
matT_1306_04_06C
Antilles, Guyane • Juin 2013
Exercice 3 • 5 points
Un guide de randonnée en montagne décrit les itinéraires possibles autour d’un pic rocheux.
La description des itinéraires est donnée par le graphe ci-dessous.
Les sommets de ce graphe correspondent aux lieux remarquables.
Les arêtes de ce graphe représentent les sentiers possibles entre ces lieux.
Légende :
① Départ ② Passerelle
③ Roche percée ④ Col des 3 vents
⑤ Pic Rouge ⑥ Refuge
⑦ Col Vert ⑧ Pont Napoléon
⑨ Cascade des Anglais ⑩ Arrivée
la matrice d’adjacence associée à ce graphe, les sommets étant pris dans l’ordre. On donne ci-dessous 
:
Déterminer l’itinéraire allant de D à A le plus court en temps.
On fera apparaître la démarche en utilisant un algorithme. (1,5 point)
Durée conseillée : 45 min.
Les thèmes en jeu
Graphe pondéré • Matrice associée à un graphe • Chaîne de longueur donnée • Chaîne eulérienne.
Les conseils du correcteur
représentent le nombre de trajets entre deux points empruntant 5 sentiers.
> 1. Déterminer une chaîne passant par tous les sommets d’un graphe
Notez bien
Ces itinéraires n’empruntent pas tous les sentiers : par exemple, les sentiers de 1 à 4, de 2 à 5 ne sont pas empruntés par ces itinéraires.
Des itinéraires allant de D à A et passant une seule fois par tous les sommets du graphe sont :
> 2. Déterminer si un graphe admet une chaîne eulérienne
Info
Le degré d’un sommet d’un graphe est le nombre d’arêtes dont ce sommet est l’une des extrémités.
Le graphe est connexe. On cherche les sommets de degré impair.
Les sommets 1, 6, 7 et 9 sont de degré 3 (les autres sommets sont de degré pair).
Le graphe comporte 4 sommets de degré impair ; par conséquent, d’après le théorème d’Euler, il n’admet pas de chaîne eulérienne.
> 3. a) Interpréter un coefficient d’une puissance de la matrice associée à un graphe
Le nombre situé sur la deuxième ligne et la quatrième colonne de la matrice 
est le nombre de trajets du sommet 2 au sommet 4 (ou inversement) constitués de 5 sentiers.
b) Déterminer sur un graphe le nombre de chaînes de longueur donnée
Pour trouver le nombre d’itinéraires allant de D (sommet 1) à A (sommet 10) et empruntant 5 sentiers, il suffit de regarder le coefficient de 
situé sur la première ligne et la 10e colonne. Ce coefficient est 31.
Le Pic Rouge est le sommet 5, un itinéraire allant de D (sommet 1) à A (sommet 10) en 5 étapes et passant par le Pic Rouge (sommet 5) est :
> 4. Déterminer sur un graphe une chaîne de « poids » minimal
Pour déterminer l’itinéraire le plus rapide de D à A, on utilise l’algorithme de Dijkstra, qui peut être résumé par le tableau suivant :
|
1 (D) |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 (A) |
|
0 (1) |
35 (1) |
15 (1) |
90 (1) |
|
|
|
|
|
|
|
|
35 (1) |
|
90 (1) |
|
40 (3) |
|
105 (3) |
|
|
|
|
|
|
90 (1) |
85 (2) |
40 (3) |
|
105 (3) |
|
|
|
|
|
|
90 (1) |
80 (6) |
|
|
95 (6) |
|
|
|
|
|
|
90 (1) |
|
|
90 (5) |
95 (6) |
|
|
|
|
|
|
|
|
|
90 (5) |
95 (6) |
135 (4) |
|
|
|
|
|
|
|
|
|
95 (6) |
110 (7) |
|
|
|
|
|
|
|
|
|
|
110 (7) |
135 (8) |
|
|
|
|
|
|
|
|
|
|
130 (9) |
Notez bien
Cet itinéraire est formé de 6 sentiers.
Il existe d’autres trajets de D à A comportant moins d’étapes, mais d’une durée plus longue : par exemple, 1-3-6-8-10 est formé de 4 sentiers, mais dure 135 minutes.
L’itinéraire le plus rapide de D à A est donc :
c’est-à-dire :
Départ – Roche percée – Refuge – Pic rouge – Col vert – Cascade des Anglais