Étude d’un réseau d’autoroutes et trajet de coût minimal

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2013 | Académie : Moyen-Orient
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Étude d’un réseau d’autoroutes et trajet de coût minimal
 
 

Matrices et graphes • Plus court chemin

Corrigé

35

Ens. de Spécialité

matT_1305_09_06C

 

Liban • Mai 2013

Exercice 4 • 5 points

Le graphe ci-dessous représente les autoroutes entre les principales villes du Sud de la France : Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Montpellier (P), Brive (R), Toulouse (T), Valence (V) et Biarritz (Z).


 

Pour cette question, on justifiera chaque réponse :

>1.a) Déterminer l’ordre du graphe. (0,5 point)

b) Déterminer si le graphe est connexe. (0,5 point)

c) Déterminer si le graphe est complet. (0,5 point)

>2. Un touriste atterrit à l’aéroport de Lyon et loue une voiture. Déterminer, en justifiant, s’il pourra visiter toutes les villes en empruntant une et une seule fois chaque autoroute. (1 point)

>3. Il décide finalement d’aller seulement de Lyon à Biarritz. On note N la matrice associée au graphe, les sommets étant rangés dans l’ordre alphabétique B, C, L, M, P, R, T, V, Z.

Voici les matrices N et N3 :

et

a) En détaillant le calcul, déterminer le coefficient de la troisième ligne et dernière colonne de la matrice N4. (0,5 point)

b) En donner une interprétation. (0,5 point)

>4. Sur les arêtes du graphe sont maintenant indiqués les prix du péage en euros :


 

a) À l’aide de l’algorithme de Dijkstra, déterminer le chemin que doit prendre le touriste pour minimiser le coût des péages de Lyon à Biarritz. (1 point)

b) Déterminer le coût, en euros, de ce trajet. (0,5 point)

Durée conseillée : 45 min.

Les thèmes en jeu

Graphe pondéré • Matrice associée à un graphe • Chaîne eulérienne.

Les conseils du correcteur

>1. Utilisez les définitions : ordre d’un graphe, graphe connexe, graphe complet.

>2. Déterminez le degré des sommets et utilisez le théorème d’Euler.

>3.b) Chaque coefficient de la matrice donne le nombre de chemins de 4 étapes entre deux sommets.

>4.a) Un chemin qui minimise le coût du péage ne comporte pas nécessairement un nombre d’arêtes minimal.

Corrigé

>1.a) Déterminer l’ordre d’un graphe

Le graphe donné comporte 9 sommets correspondant aux 9 villes considérées.

Donc le graphe donné est d’ordre 9.

b) Déterminer si un graphe est connexe

Il existe une chaîne entre deux sommets quelconques ; on peut se rendre d’une ville quelconque à une autre en empruntant les autoroutes considérées.

Donc le graphe est connexe.

c) Déterminer si un graphe est complet

Il n’existe pas d’arête d’extrémités B et M ; concrètement, il n’existe pas d’autoroute « directe » entre Bordeaux et Marseille.

Donc le graphe n’est pas complet.

>2. Déterminer si un graphe possède une chaîne eulérienne

 

Info

Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes.

Un touriste partant de Lyon pourra visiter toutes les villes en empruntant une fois et une seule chaque autoroute si et seulement si le graphe possède une chaîne eulérienne dont l’une des extrémités est L.

 

Info

Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.

D’après le théorème d’Euler, pour qu’il existe une chaîne eulérienne dont L est l’une des extrémités, il faut que le graphe ait au plus deux sommets de degré impair.

Or B, R, C et V sont de degré 3.

 

Notez bien

La réponse est la même quelle que soit la ville de départ.

Puisqu’il y a au moins quatre sommets de degré impair, le graphe ne comporte pas de chaîne eulérienne. Un touriste partant de Lyon ne pourra donc pas visiter toutes les villes en empruntant une fois et une seule chaque autoroute.

>3.a) Déterminer un coefficient du produit de deux matrices

Si on écrit , le coefficient de la troisième ligne et dernière colonne de la matrice s’obtient à partir de la troisième ligne de N et de la dernière colonne de  :

b) Donner une interprétation concrète d’un coefficient d’une matrice

 

Notez bien

Le coefficient de la ligne et colonne de donne le nombre de chemins permettant d’aller du sommet au sommet en étapes.

D’après le résultat précédent, il existe 4 chemins de Lyon (troisième sommet) à Biarritz (dernier sommet) formés de 4 étapes.

>4.a) Rechercher sur un graphe pondéré un chemin de « poids » minimal

 

Info

Dans cette question, on utilise un graphe pondéré. Le « poids » attribué à chaque arête est le prix du péage en euros entre les deux villes reliées par cette arête.

On utilise l’algorithme de Dijkstra pour déterminer le chemin « le moins cher » de Lyon à Biarritz.

Cet algorithme peut se traduire par le tableau suivant :

 

B

C

L

M

P

R

T

V

Z

0

10,70 (L)

7,10 (L)

10,70 (L)

22,80 (V)

23,30 (V)

22,80 (V)

19,30 (C)

22,20 (C)

22,80 (V)

22,20 (C)

38,90 (P)

33,70 (R)

22,80 (V)

36,80 (R)

33,70 (R)

36,80 (R)

36,80 (R)

38,10 (B)

 

On en déduit que le chemin de Lyon à Biarritz qui minimise le coût des péages est :

c’est-à-dire LyonClermont-FerrandBriveBordeauxBiarritz.

b) Déterminer un « poids » minimal sur un graphe pondéré

D’après l’algorithme de Dijkstra, le coût minimal de Lyon à Biarritz est 38,10 €.