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

Merci !

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.