Déplacements et temps de trajet entre les zones d’intérêt d’une commune

Merci !
Retour

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2013 | Académie : Afrique
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Déplacements et temps de trajet entre les zones d’intérêt d’une commune
 
 

Matrices et graphes • Plus court chemin

Corrigé

36

Ens. de Spécialité

matT_1306_01_04C

 

Afrique • Juin 2013

Exercice 2 • 5 points

Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d’activités d’une municipalité. Une arête reliant deux de ces sommets indique l’existence d’une voie d’accès principale entre deux lieux correspondants.


 

> 1. Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l’ordre alphabétique). (0,75 point)

> 2. a)  Donner la matrice  associée au graphe (les sommets seront mis dans l’ordre alphabétique). (0,5 point)

b) On donne la matrice .

Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant et , puis donner leur liste. (1 point)

> 3. Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d’accès principales de ce quartier sans emprunter plusieurs fois la même voie. Montrer qu’un tel parcours est possible. (0,75 point)

> 4. Dans le graphe ci-dessous, les valeurs indiquent, en minutes, les durées moyennes des trajets entre les différents lieux via les transports en commun.


 

Ce même candidat se trouve à la mairie () quand on lui rappelle qu’il a un rendez-vous avec le responsable de l’hôpital situé en zone G.

a) En utilisant l’algorithme de Dijkstra, déterminer le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous. (1,5 point)

b) Combien de temps faut-il prévoir pour effectuer 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 de longueur donnée • Chaîne eulérienne.

Les conseils du correcteur

> 1. Le degré d’un sommet d’un graphe est le nombre d’arêtes dont ce sommet est l’une des extrémités.

> 2. a) Les coefficients de la matrice associée à un graphe sont égaux à 0 ou à 1 ; cette matrice est symétrique par rapport à sa diagonale principale car le graphe n’est pas orienté.

> 2. b) Les coefficients de la matrice donnent le nombre de chemins de longueur 3 entre deux sommets donnés.

> 3. Déterminer s’il existe un parcours passant par toutes les voies sans emprunter plusieurs fois la même revient à déterminer s’il existe une chaîne eulérienne. Trouvez le nombre de sommets de degré impair et utilisez le théorème d’Euler : un graphe comporte une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2.

> 4. a)  Un chemin de durée minimale ne comporte pas nécessairement un nombre minimal d’arêtes.

Corrigé

> 1. Déterminer le degré des sommets d’un graphe

 

Sommet

A

B

C

D

E

F

G

Degré

2

4

5

5

4

4

2
 
 

Notez bien

Sur la diagonale de M, tous les termes sont égaux à 0 car le graphe ne comporte aucune boucle.

> 2.a) Déterminer la matrice associée à un graphe

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

Le nombre de chemins de longueur 3, c’est-à-dire formés de 3 arêtes, reliant A (premier sommet) à F (sixième sommet dans l’ordre alphabétique) est le coefficient de situé sur la première ligne et la sixième colonne, égal au coefficient situé sur la sixième ligne et la première colonne.

Ce nombre est égal à 5, donc il y a 5 chemins de longueur 3 reliant A à F.

Ces chemins sont :

 

Info

Un tel chemin est par exemple :

CBACEBDCFEDFGD

(le graphe comporte 13 arêtes).

Il n’existe pas de parcours partant et arrivant au même sommet et passant une fois et une seule par chacune des voies.

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

Un parcours empruntant une fois et une seule chacune des voies est une chaîne eulérienne du graphe.

On a vu à la question 1. que le graphe possède deux sommets de degré impair, C et D. De plus, le graphe est connexe. D’après le théorème d’Euler, ce graphe admet une chaîne eulérienne qui n’est pas un cycle, c’est-à-dire dont les extrémités sont deux sommets différents, ici C et D.

Il est donc possible de parcourir une fois et une seule chacune des voies en partant de C et en allant en D, ou l’inverse.

> 4.a) Rechercher sur un graphe pondéré un chemin de durée minimale

On utilise l’algorithme de Dijkstra pour déterminer le chemin le plus rapide de A à G. Cet algorithme peut se traduire par le tableau suivant :

 

A

B

C

D

E

F

G

0

∞

∞

∞

∞

∞

∞

 

8 (A)

4 (A)

∞

∞

∞

∞

 

8 (A)

 

20 (C)

16 (C)

24 (C)

∞

 

 

 

12 (B)

16 (C)

24 (C)

∞

 

 

 

 

16 (C)

24 (C)

32 (D)

 

 

 

 

 

20 (E)

32 (D)

 

 

 

 

 

 

28 (F)
 

Le chemin le plus rapide de A à G est donc :

b) Déterminer la durée d’un trajet sur un graphe

 

Notez bien

Ce trajet est formé de quatre arêtes. Il existe des trajets de A à G formés de trois arêtes (par exemple A – B – D – G), mais leur durée est supérieure à 28 minutes.

Pour trouver la durée de ce parcours, on additionne les durées des différents trajets. La durée totale est donc 28 minutes.