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.

Corrigé

Corrigé

partie A

 1. a) Déterminer si un graphe est connexe

Entre deux sommets quelconques, il existe toujours au moins une chaîne, aucun sommet n’est isolé, donc le graphe G est connexe.

b) Étudier sur un graphe donné l’existence d’une chaîne eulérienne

D’après le théorème d’Euler, le graphe connexe G admet une chaîne eulérienne si et seulement s’il possède exactement 0 ou 2 sommets de degré impair, les autres sommets étant de degré pair.

On peut résumer dans un tableau les degrés des différents sommets :

Sommet

A

B

C

D

E

F

G

H

Degré

2

4

2

2

4

4

2

4

Tous les sommets sont de degré pair, donc le graphe G admet une chaîne eulérienne.

On peut même en déduire que G possède (au moins) un cycle eulérien, c’est-à-dire une chaîne eulérienne dont l’origine et l’extrémité sont confondues.

 2. Déterminer le nombre de chemins de longueur donnée entre deux sommets d’un graphe

Les sommets étant pris dans l’ordre alphabétique, E est le sommet 5 et B le sommet 2.

Notez bien

Il n’est pas demandé de donner ces chemins. Le graphe G n’étant pas orienté, les matrices 3316332-Eqn205 et 3316332-Eqn206 sont symétriques, donc le coefficient situé à l’intersection de la 5e ligne et de la 2e colonne est égal au coefficient situé à l’intersection de la 2e ligne et de la 5e colonne.

Le nombre de chemins de longueur 3 (c’est-à-dire comportant 3 arêtes) reliant E à B est donc le coefficient de 3316332-Eqn207 situé à l’intersection de la 5e ligne et de la 2e colonne, c’est-à-dire 5. Il y a donc 5 chemins formés de 3 arêtes et reliant E à B.

partie B

 1. a) Étudier l’existence d’un itinéraire empruntant tous les sentiers

Un itinéraire au départ du refuge A, passant par tous les refuges et empruntant une fois et une seule chacun des sentiers est un cycle eulérien (on suppose que cet itinéraire se termine également au refuge A).

Or d’après la partie A, le graphe G possède un cycle eulérien, donc un tel itinéraire existe, par exemple :

3316332-Eqn207bis

b) Étudier l’existence d’un itinéraire de longueur donnée

D’après la question 2. a) de la partie A, il existe 5 itinéraires de trois jours reliant le refuge E au refuge B.

 2. Déterminer un itinéraire de longueur minimale

Pour déterminer l’itinéraire le plus court (en kilomètres) du refuge A au refuge H, on utilise l’algorithme de Dijkstra, dont les étapes successives sont résumées dans le tableau suivant :

A

B

C

D

E

F

G

H

0

3316332-Eqn209

3316332-Eqn210

3316332-Eqn211

3316332-Eqn212

3316332-Eqn213

3316332-Eqn214

3316332-Eqn215

 

12 (A)

3316332-Eqn216

14 (A)

3316332-Eqn217

3316332-Eqn218

3316332-Eqn219

3316332-Eqn220

   

3316332-Eqn221

14 (A)

3316332-Eqn222

21 (B)

28 (B)

33 (B)

   

3316332-Eqn223

 

24 (D)

21 (B)

28 (B)

33 (B)

   

31 (F)

 

24 (D)

 

28 (B)

33 (B)

   

31 (F)

     

28 (B)

32 (F)

   

31 (F)

       

32 (F)

             

32 (F)

On en déduit que l’itinéraire le plus court de A à H est :

3316332-Eqn207ter

Sa longueur est 32 kilomètres.