Sentiers et itinéraires en montagne

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2013 | Académie : Antilles, Guyane
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Sentiers et itinéraires en montagne
 
 

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

>1. Donner un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois, mais n’empruntant pas forcément tous les sentiers. (1 point)

>2. Existe-t-il un itinéraire allant de D à A utilisant tous les sentiers une seule fois ? Justifier votre réponse. (1 point)

>3. On note  la matrice d’adjacence associée à ce graphe, les sommets étant pris dans l’ordre. On donne ci-dessous  :

a) Que représente le nombre 89 situé sur la deuxième ligne et la quatrième colonne ? (0,5 point)

b) Déterminer le nombre d’itinéraires allant de D à A empruntant 5 sentiers. Citer un tel itinéraire passant par le Pic Rouge. (1 point)

>4. On a complété ci-après le graphe décrivant les itinéraires avec les temps de parcours en minutes pour chacun des sentiers.


 

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

>2. Utilisez le théorème d’Euler.

>3. Les coefficients de la matrice  représentent le nombre de trajets entre deux points empruntant 5 sentiers.

>4. Utilisez l’algorithme de Dijkstra.

Corrigé

>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.

Donc il n’existe aucun itinéraire utilisant une fois et une seule chaque sentier.

>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.

Il existe donc 89 manières différentes d’aller du sommet 2 au sommet 4 en parcourant 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.

Donc il existe 31 itinéraires différents de D à A constitués de 5 sentiers.

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 - Arrivée

Le temps correspondant est 130 minutes.