Graphes et itinéraires de randonnée

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2015 | Académie : France métropolitaine

 

France métropolitaine • Juin 2015

Exercice 2 • 5 points

Graphes et itinéraires de randonnée

partie A

On considère le graphe 3316332-Eqn41 ci-dessous :

matT_1506_07_01C_01

 1. Déterminer en justifiant si ce graphe :

a) est connexe ; (0,5 point)

b) admet une chaîne eulérienne. (0,5 point)

 2. On note 3316332-Eqn42 la matrice d’adjacence associée à ce graphe en prenant les sommets dans l’ordre alphabétique. On donne :

3316332-Eqn43

Donner, en justifiant, le nombre de chemins de longueur 3 reliant E à B. (0,5 point)

partie B

Un club alpin souhaite proposer à ses membres des randonnées de plusieurs jours dans les Alpes. À cet effet, huit refuges notés A, B, C, D, E, F, G et H ont été sélectionnés.

Le graphe 3316332-Eqn44 de la partie A permet de visualiser les différents itinéraires possibles, les sommets représentant les refuges et les arêtes schématisant tous les sentiers de randonnée balisés les reliant.

 1. D’après l’étude effectuée dans la partie A, le club alpin est-il en mesure de proposer :

a) un itinéraire au départ du refuge A qui passerait par tous les refuges en empruntant une fois et une seule fois chacun des sentiers ? Si oui, proposer un tel itinéraire ; (1 point)

b) des itinéraires de trois jours (un jour correspondant à une liaison entre deux refuges) reliant le refuge E au refuge B ? Si oui, combien peut-il en proposer ? (1 point)

 2. Le graphe 3316332-Eqn45 est complété ci-dessous par la longueur en kilomètres de chacun des sentiers.

matT_1506_07_01C_02

Le club alpin désire aussi proposer à ses membres l’itinéraire le plus court reliant A à H.

Déterminer cet itinéraire et en préciser la longueur en kilomètres. (1,5 point)

Les clés du sujet

Durée conseillée : 45 minutes

Les thèmes en jeu

Matrice • Graphe pondéré • Chaîne de longueur donnée • Chaîne eulérienne • Plus court chemin.

Les conseils du correcteur

Partie A

 1. b) Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes ; utilisez le théorème d’Euler.

 2. Le nombre de chemins de longueur 3 reliant E à B est l’un des coefficients de la matrice 3316332-Eqn101.

Partie B

 2. Utilisez l’algorithme de Dijkstra.