Étude d’un réseau et trajet minimal

Merci !

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

Matrices et graphes • Plus court chemin

Corrigé

34

Ens. de Spécialité

matT_1304_12_06C

 

Pondichéry • Avril 2013

Exercice 2 • 5 points

Les parties A et B peuvent être traitées indépendamment.

On considère le graphe Γ ci-dessous :


 

PARTIE A

>1. Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui, donner une telle chaîne. (1 point)

>2. Ce graphe admet-il un cycle eulérien ? Justifier la réponse. Si oui, donner un tel cycle. (1 point)

>3. Donner la matrice M associée au graphe Γ. Les sommets seront pris dans l’ordre alphabétique : A, B, C, D, E, F, G. (1 point)

PARTIE B

Une région est munie d’un réseau de trains, représenté par le graphe Γ ci-après.

Les stations sont symbolisées par les sommets A, B, C, D, E, F et G. Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.


 

>1. Déterminer le plus court chemin en minutes, reliant la gare B à la gare G. Justifier la réponse grâce à un algorithme. (1,5 point)

>2. Quelle est la longueur en minutes de ce chemin ? (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

Partie A

>1. Vous pouvez utiliser le théorème d’Euler : regardez si le graphe est connexe et déterminez le degré de chaque sommet.

>2. Regardez si le graphe Γ possède des sommets de degré impair.

>3. Le graphe Γ est un graphe simple non orienté ; la matrice associée M est symétrique et ses coefficients sont 0 ou 1.

Partie B

>1. On peut utiliser par exemple l’algorithme de Dijkstra.

Corrigé

PARTIE A

>1. Déterminer si un graphe comporte une chaîne eulérienne

Une chaîne eulérienne d’un graphe est une chaîne qui contient une fois et une seule chaque arête du graphe.

D’après le théorème d’Euler, un graphe connexe contient une chaîne eulérienne si et seulement si il possède 0 ou 2 sommet(s) de degré impair.

On peut récapituler les degrés des sommets du graphe Γ dans un tableau :

 

Sommet

A

B

C

D

E

F

G

Degré

2

4

4

5

4

4

3

 
 

Notez bien

On peut montrer que dans un graphe connexe ayant exactement deux sommets de degré impair, il existe une chaîne eulérienne reliant ces deux sommets.

Il y a deux sommets de degré impair, D et G, donc d’après le théorème d’Euler, le grapheΓcontient une chaîne eulérienne.

Deux exemples de chaînes eulériennes :

D - B - A - C - B - E - F - D - C - F - G - E - D – G

D - B - A - C - B - E - D - C - F - D - G - E - F – G

>2. Déterminer si un graphe comporte un cycle eulérien

Un cycle eulérien d’un graphe est une chaîne eulérienne qui est un cycle, c’est-à-dire dont le sommet de départ et le sommet d’arrivée sont confondus.

Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

Or le graphe Γ possède exactement deux sommets de degré impair (D et G), donc le grapheΓne possède pas de cycle eulérien.

>3. Déterminer la matrice associée à un graphe

 

Notez bien

La matrice associée à un graphe non orienté est symétrique. Si ce graphe n’est pas pondéré, la matrice ne comporte que des 0 et des 1 ; le coefficient situé à la iième ligne et jième colonne de M est égal à 1 s’il existe une arête entre le sommet i et le sommet j, à 0 sinon.

La matrice associée au graphe Γ est :

PARTIE B

>1. Rechercher sur un graphe pondéré un chemin de « longueur » minimale

Pour déterminer le plus court chemin en minutes de la gare B à la gare G, on utilise l’algorithme de Dijkstra :

 

A

B

C

D

E

F

G

4 (B)

0 (B)

7 (B)

18 (B)

21 (B)

4 (B)

7 (B)

18 (B)

21 (B)

7 (B)

17 (C)

21 (B)

(C)

17 (C)

21 (B)

29 (D)

48 (D)

21 (B)

29 (D)

38 (E)

29 (D)

36 (F)

 

On en déduit que le plus court chemin, en minutes, de B à G est :

 

Attention

Ce trajet minimise le temps en minutes de B à G, pas le nombre d’étapes. En effet, il comporte 4 étapes, alors qu’il est possible d’aller de B à G en deux ou trois étapes mais avec un temps supérieur à 36 minutes.

>2. Déterminer un temps de trajet minimal à partir d’un graphe pondéré

La longueur en minutes du chemin B – C – D – F – G est :

7 + 10 + 12 + 7

soit 36 minutes.