Étude à l’aide d’un graphe de déplacements lors d’une campagne électorale

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2014 | Académie : Amérique du Nord
Corpus Corpus 1
Étude à l&rsquo aide d&rsquo un graphe de déplacements lors d&rsquo une campagne électorale

Graphes, &laquo plus court chemin &raquo

matT_1405_02_09C

Ens. de spécialité

33

CORRIGE

Amérique du Nord &bull Mai 2014

Exercice 4 &bull 5 points

Lors d&rsquo une campagne électorale, un homme politique doit effectuer une tournée dans les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier. Le graphe ci-dessous représente les différentes villes de la tournée et les tronçons d&rsquo autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d&rsquo autoroute par une arête) :


&nbsp

partie a

&gt 1. Déterminer, en justifiant, si le graphe est :

a) complet  (0,5 point)

b) connexe. (0,5 point)

&gt 2. a) Justifier qu&rsquo il est possible d&rsquo organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d&rsquo autoroute. (0,75 point)

b) Citer un trajet de ce type. (0,5 point)

&gt 3. On appelle la matrice d&rsquo adjacence associée au graphe (les sommets étant pris dans l&rsquo ordre alphabétique).

a) Déterminer la matrice . (0,5 point)

b) On donne la matrice .

Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant E à H.

Préciser ces chemins. (1 point)

partie b

Des contraintes d&rsquo organisation obligent cet homme politique à se rendre dans la ville F après la ville A.

Le graphe est complété ci-dessous par les longueurs en kilomètre de chaque tronçon d&rsquo autoroute.


&nbsp

Déterminer, en utilisant l&rsquo algorithme de Dijkstra, le trajet autoroutier le plus court pour aller de A à F. Préciser la longueur en kilomètre de ce trajet. (1,25 point)

Les clés du sujet

Les thèmes en jeu

Matrice &bull Graphe pondéré &bull Chaîne de longueur donnée &bull Chaîne eulérienne &bull Plus court chemin.

Les conseils du correcteur

Partie A

&gt 2. a) Utilisez le théorème d&rsquo Euler pour déterminer si le graphe possède une chaîne eulérienne.

&gt 3. a) Les coefficients de la matrice d&rsquo adjacence associée à un graphe sont égaux à 0 ou 1.

b) Chaque coefficient de la matrice est égal au nombre de chemins de longueur 3 entre deux sommets donnés.