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
&nbsp
Unit 1 - | Corpus Sujets - 1 Sujet
&nbsp
Déplacements et temps de trajet entre les zones d&rsquo intérêt d&rsquo une commune
&nbsp
&nbsp

Matrices et graphes &bull Plus court chemin

Corrigé

36

Ens. de Spécialité

matT_1306_01_04C

&nbsp

Afrique &bull Juin 2013

Exercice 2 &bull 5 points

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


&nbsp

&gt 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&rsquo ordre alphabétique). (0,75 point)

&gt 2.a)  Donner la matrice  associée au graphe (les sommets seront mis dans l&rsquo 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)

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

&gt 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.


&nbsp

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

a) En utilisant l&rsquo 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é &bull Matrice associée à un graphe &bull Chaîne de longueur donnée &bull Chaîne eulérienne.

Les conseils du correcteur

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

&gt 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&rsquo est pas orienté.

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

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

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