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
&nbsp
Unit 1 - | Corpus Sujets - 1 Sujet
&nbsp
Sentiers et itinéraires en montagne
&nbsp
&nbsp

Matrices et graphes &bull Plus court chemin

Corrigé

37

Ens. de Spécialité

matT_1306_04_06C

&nbsp

Antilles, Guyane &bull Juin 2013

Exercice 3 &bull 5 points

Un guide de randonnée en montagne décrit les itinéraires possibles autour d&rsquo 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.


&nbsp

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

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

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

&gt 3. On note  la matrice d&rsquo adjacence associée à ce graphe, les sommets étant pris dans l&rsquo 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&rsquo itinéraires allant de D à A empruntant 5 sentiers. Citer un tel itinéraire passant par le Pic Rouge. (1 point)

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


&nbsp

Déterminer l&rsquo 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é &bull Matrice associée à un graphe &bull Chaîne de longueur donnée &bull Chaîne eulérienne.

Les conseils du correcteur

&gt 2. Utilisez le théorème d&rsquo Euler.

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

&gt 4. Utilisez l&rsquo algorithme de Dijkstra.