Étude à l’aide d’un graphe de la mobilité d’étudiants et recherche d’un trajet minimal

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2013 | Académie : France métropolitaine
Corpus Corpus 1
Étude à l’aide d’un graphe de la mobilité d’étudiants et recherche d’un trajet minimal

Graphes, « plus court chemin »

matT_1309_07_03C

Ens. de spécialité

35

CORRIGE

France métropolitaine • Septembre 2013

Exercice 2 • 5 points

Les parties A et B de cet exercice sont indépendantes.

Un lycée d’une grande ville de province organise un forum des grandes écoles de la région pour aider ses élèves dans leurs choix d’orientation post-bac.

PARTIE A

Une des écoles a effectué une étude sur la mobilité des étudiants de la promotion 2008 en ce qui concerne les choix de carrière.

Elle a relevé qu’en 2008, à la fin de leurs études, 25 % des diplômés sont partis travailler à l’étranger, alors que le reste de la promotion a trouvé du travail en France.

On a observé ensuite qu’à la fin de chaque année, 20 % des personnes ayant opté pour l’étranger reviennent sur un poste en France, alors que 10 % des personnes travaillant en France trouvent un poste à l’étranger. On considère que cette situation perdure.

On note la matrice correspondant à l’état probabiliste en , avec la probabilité que la personne travaille à l’étranger, celle qu’elle travaille en France.

Ainsi .

>1. Proposer le graphe probabiliste associé à cette situation. On désignera par E (étranger) et F (France) les deux sommets. (0,5 point)

>2. Donner la matrice de transition M associée en prenant les sommets dans l’ordre E, puis F. (0,5 point)

>3. Montrer qu’en 2011, la proportion des étudiants de la promotion 2008 travaillant à l’étranger est de 30,475 %. (0,75 point)

>4. Déterminer l’état stable du graphe probabiliste et interpréter le résultat obtenu. (1,25 point)

PARTIE B

Pour clôturer cette journée, un groupe de lycéens musiciens a décidé d’organiser un concert.

Ils décident de faire le tour de tous les lycées de la ville et de distribuer des prospectus sur le trajet pour faire de la publicité pour cette soirée.

Les membres du groupe ont établi le graphe ci-dessous. Les arêtes sont pondérées par les durées des trajets entre deux sommets consécutifs, exprimées en minutes.


 

>1. Existe-t-il un trajet d’un lycée à un autre permettant de parcourir toutes les rues une fois et une seule ? Si oui, donner un tel trajet, si non expliquer pourquoi. (1 point)

>2. Arrivé en retard au lycée A, un membre du groupe veut trouver le chemin le plus rapide pour rejoindre ses camarades au lycée G. Quel trajet peut-il prendre ? Quelle est alors la durée du parcours ? (1 point)

Les clés du sujet

Les thèmes en jeu

Graphe probabiliste • Matrice • Graphe pondéré • Chaîne eulérienne • Plus court chemin.

Les conseils du correcteur

Partie A

>1. Dans un graphe probabiliste, les arêtes issues d’un même sommet sont pondérées par des probabilités conditionnelles de somme égale à 1.

>2. Les coefficients de la matrice de transition associée à un graphe probabiliste sont les probabilités portées par les arêtes de ce graphe ; la somme des coefficients d’une ligne est égale à 1.

Partie B

>2. Utilisez l’algorithme de Dijkstra.

Corrigé
Corrigé

PARTIE A

>1. Représenter une situation par un graphe probabiliste

La situation décrite peut être représentée par le graphe suivant :


 

>2. Donner la matrice de transition associée à un graphe probabiliste

Par définition, la matrice de transition d’un graphe probabiliste est la matrice M telle que, pour tout entier naturel  :

.

D’après l’énoncé :

Donc la matrice de transition du graphe précédent est :

>3. Utiliser la matrice de transition d’un graphe probabiliste

 ; on cherche donc .

Donc en 2011, la proportion des étudiants de la promotion 2008 travaillant à l’étranger est de 30,475 %.

>4. Déterminer et interpréter l’état stable d’un graphe probabiliste

Un état stable est défini par , soit :

, qui équivaut à , c’est-à-dire :

.

De plus , donc .

On en déduit que l’état stable est.

Cela signifie qu’à long terme,des étudiants partent travailler à l’étranger etrestent en France.

PARTIE B

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

Un trajet d’un lycée à un autre permettant de parcourir toutes les rues une fois et une seule est une chaîne eulérienne du graphe. Or, un graphe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2.

Le graphe proposé a 4 sommets de degré impair : B, C et G de degré 3, D de degré 5. Il n’admet donc pas de chaîne eulérienne.

Donc il n’existe pas de trajet d’un lycée à un autre permettant de parcourir toutes les rues une fois et une seule.

>2. Déterminer un plus court chemin sur un graphe

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

 

A

B

C

D

E

F

G

0

16 (A)

30 (A)

30 (A)

56 (B)

62 (D)

59 (D)

56 (B)

90 (D)

62 (D)

59 (D)

84 (F)

62 (D)

84 (F)

84 (F)

 

Le chemin le plus rapide du sommet A au sommet G est donc :

A – B – F – G.

La durée de ce parcours est 84 minutes.