É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’aide d’un graphe de déplacements lors d’une campagne électorale

Graphes, « plus court chemin »

matT_1405_02_09C

Ens. de spécialité

33

CORRIGE

Amérique du Nord • Mai 2014

Exercice 4 • 5 points

Lors d’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’autoroute reliant ces villes (une ville est représentée par un sommet, un tronçon d’autoroute par une arête) :


 

partie a

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

a) complet ; (0,5 point)

b) connexe. (0,5 point)

>2. a) Justifier qu’il est possible d’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’autoroute. (0,75 point)

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

>3. On appelle la matrice d’adjacence associée au graphe (les sommets étant pris dans l’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’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’autoroute.


 

Déterminer, en utilisant l’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 • Graphe pondéré • Chaîne de longueur donnée • Chaîne eulérienne • Plus court chemin.

Les conseils du correcteur

Partie A

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

>3. a) Les coefficients de la matrice d’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.

Corrigé
Corrigé

partie a

>1.a) Déterminer si un graphe est complet

Il n’existe pas d’arête entre les sommets A et E (les villes A et E ne sont pas reliées par un tronçon d’autoroute).

Donc le graphen’est pas complet.

b) Déterminer si un graphe est connexe

Deux sommets quelconques sont reliés par une arête ou par une chaîne ; il n’existe pas de sommet « isolé », on peut aller d’une ville à une autre en empruntant un ou plusieurs tronçons d’autoroute.

Donc le grapheest connexe.

>2.a) Déterminer si un graphe possède une chaîne eulérienne

Il est possible d’organiser la tournée en passant au moins une fois par chaque ville, et en empruntant une fois et une seule chaque tronçon d’autoroute si et seulement si le graphe possède une chaîne eulérienne.

D’après le théorème d’Euler, un graphe connexe possède une chaîne eulérienne si et seulement si le nombre de sommets de ce graphe de degré impair (c’est-à-dire extrémités d’un nombre impair d’arêtes) est égal à 0 ou 2. On peut résumer dans un tableau les degrés des différents sommets :

 

Sommet

A

B

C

D

E

F

G

H

Degré

2

3

4

3

4

2

4

4

 

Notez bien

Une chaîne eulérienne peut passer plusieurs fois par le même sommet.

Il y a exactement deux sommets de degré impair, B et D, donc le graphe possède une chaîne eulérienne. Il est donc possible d’organiser la tournée en passant au moins une fois par chaque ville, et en empruntant une fois et une seule chaque tronçon d’autoroute.

b) Citer une chaîne eulérienne d’un graphe

Une chaîne eulérienne a nécessairement comme extrémités B et D, qui sont les deux sommets de degré impair.

Un exemple de trajet qui passe au moins une fois par chaque ville et emprunte une fois et une seule chaque tronçon d’autoroute est :

>3.a) Déterminer la matrice d’adjacence d’un graphe

Notez bien

Le coefficient situé à l’intersection de la ligne et la colonne de est égal à 0 s’il n’y a pas d’arête d’extrémités les sommets et , à 1 s’il y en a une.

La matrice d’adjacence du graphe est :

b) Déterminer le nombre de chemins de longueur donnée entre deux sommets

Les sommets (c’est-à-dire les villes de la tournée) sont rangés dans l’ordre alphabétique, donc E est le sommet numéro 5 et H le sommet numéro 8.

Le nombre de chemins de longueur 3 reliant E à H est donc le coefficient de la matrice situé à l’intersection de la ligne 5 et de la colonne 8 (ou de la ligne 8 et de la colonne 5), c’est-à-dire 4.

On en déduit qu’il existe 4 chemins de longueur 3 reliant les sommets E et H.

Ces chemins sont :

partie b

Déterminer un plus court chemin sur un graphe et calculer sa longueur

Pour trouver le chemin le plus court du sommet A au sommet F, on utilise l’algorithme de Dijkstra, qui peut se résumer par le tableau ci-dessous :

 

A

B

C

D

E

F

G

H

0

400 (A)

600 (A)

1 000 (B)

600 (A)

800 (B)

1 000 (B)

800 (B)

1 500 (D)

1 000 (B)

1 400 (E)

1 500 (D)

1 400 (E)

1 450 (C)

1 600 (G)

1 450 (C)

1 600 (G)

 

Le chemin le plus court du sommet A au sommet F est donc :

Sa longueur est 1 600 kilomètres.