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.