Baccalauréat 2019 MATHÉMATIQUES Série ES-L

sujet : Amérique du Nord 2019

Corrigé de l'exercice 2 : candidats ayant suivi l'enseignement de spécialité ES

Les deux parties de cet exercice sont indépendantes.

partie a

Pour accéder à un local d'une petite entreprise, les employés doivent choisir un code reconnu par l'automate suivant :

Une succession de lettres constitue un code possible si ces lettres se succèdent sur un chemin du graphe orienté ci-dessus, en partant du sommet ① et en sortant au sommet ⓸.
Par exemple

le mot bcbab est un mot reconnu par cet automate, et correspond au chemin 121334;
le mot abac n'est pas reconnu par cet automate.

Parmi les mots suivants, quels sont ceux qui sont reconnus par cet automate ?
abab, abc, abbcbb.
- le mot abab est un mot reconnu par cet automate, et correspond au chemin 12334;
- le mot abc n'est pas reconnu par cet automate, il ne se termine pas par b.
- le mot abbcbb est un mot reconnu par cet automate, et correspond au chemin 1234234;
Les mots reconnus par cet automate sont abab et abbcbb.
Recopier et compléter la matrice d'adjacence $M = (\begin{matrix} 0 & 2 & 1 & 0 \\ \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots \end{matrix})$ associée au graphe orienté dans laquelle les sommets sont rangés dans l'ordre croissant.
La matrice d'adjacence associée au graphe orienté dans laquelle les sommets sont rangés dans l'ordre croissant est $M = (\begin{matrix} 0 & 2 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \end{matrix})$ .
Un logiciel de calcul formel donne $M^{4} = (\begin{matrix} 5 & 3 & 10 & 5 \\ 1 & 6 & 7 & 4 \\ 1 & 3 & 4 & 2 \\ 2 & 1 & 4 & 2 \end{matrix})$ et $M^{5} = (\begin{matrix} 3 & 15 & 18 & 10 \\ 6 & 6 & 14 & 7 \\ 3 & 4 & 8 & 4 \\ 1 & 6 & 7 & 4 \end{matrix})$ . Combien de mots de 4 lettres sont-ils reconnus par l'automate ? Justifier. Quels sont-ils ?
Le nombre de chaînes de longueur 4 joignant le sommet 1 au sommet 4 est donné par le terme d'indice $m_{(14)}$ de la matrice $M^{4}$ .
Il y a donc 5 mots de 4 lettres reconnus par l'automate :
- le mot abab correspond au chemin 12334;
- le mot bbab correspond au chemin 12334;
- le mot baab correspond au chemin 13334;
- le mot acbb correspond au chemin 12134;
- le mot bcbb correspond au chemin 12134;

partie b

Dans le graphe ci-après, on a fait figurer les distances routières, exprimées en kilomètre, entre certaines grandes villes de la région Auvergne-Rhône-Alpes.

A : Aurillac	G : Grenoble
B : Bourg-en-Bresse	L : Lyon
C : Clermont-Ferrand	P : Le Puy-en-Velay
E : Saint-Étienne	V : Valence

Un technicien doit vérifier l'état des routes du réseau représenté par le graphe ci-dessus.
1. Peut-il parcourir l'ensemble du réseau en empruntant chaque route une et une seule fois ? Justifier la réponse.
  Le cycle A - P - E - V - G - B - L - C - A contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets, il existe une chaîne les reliant. Donc le graphe est connexe.
  Le graphe est connexe et il n'y a que deux sommets de degré impair G et L par conséquent, il existe des chaînes eulériennes d'extrémités G et L.
  Le technicien peut parcourir l'ensemble du réseau en empruntant chaque route une et une seule fois.
2. Si un tel parcours est possible, préciser par quelle(s) ville(s) de ce réseau routier le technicien doit commencer sa vérification.
  Le parcours est possible à condition que le technicien commence sa vérification par Grenoble ou Lyon.

Ayant terminé sa semaine de travail à Bourg-en-Bresse, le technicien souhaite retourner chez lui à Aurillac en faisant le moins de kilomètres possibles.

Déterminer, en utilisant l'algorithme de Dijkstra, le plus court chemin entre les villes de Bourg-en-Bresse et Aurillac en empruntant le réseau routier.

Déterminons un parcours de distance minimale joignant le sommet B au sommet A à l'aide de l'algorithme de Dijkstra.

B	C	E	G	L	P	V	A	Sommet sélectionné
0	∞	∞	∞	∞	∞	∞	∞	B (0)
	∞	∞	180 (B)	80 (B)	∞	∞	∞	L (80)
	260 (L)	150 (L)	180 (B)		∞	180 (L)	∞	E (150)
	260 (L)		180 (B)		230 (E)	180 (L)	∞	G (180)
	260 (L)				230 (E)	180 (L)	∞	V (180)
	260 (L)				230 (E)		∞	P (230)
	260 (L)						410 (P)	C (260)
							410 (P)	A (410)

Le sommet A étant marqué, pour lire la chaîne de poids minimal, on part de A et on "remonte" la chaîne en suivant les prédécesseurs : $A \leftarrow P \leftarrow E \leftarrow L \leftarrow B$ .

La distance minimale entre les villes de Bourg-en-Bresse et Aurillac est de 410 kilomètres. Elle est obtenue en effectuant le parcours Bourg-en-Bresse - Lyon - Saint-Étienne - Puy-en-Velay - Aurillac.

La route entre Le Puy-en-Velay et Aurillac est fermée à la circulation. Quel chemin doit-il alors emprunter ?
La route entre Le Puy-en-Velay et Aurillac étant fermée à la circulation, le technicien doit emprunter la route entre Clermont-Ferrand et Aurillac. D'après l'algorithme de Dijkstra, le plus court chemin entre les sommets B et C obtenu en remontant la chaîne des prédécesseurs est $C \leftarrow L \leftarrow B$ .
Le technicien empruntera le réseau routier Bourg-en-Bresse - Lyon - Clermont-Ferrand - Aurillac. La distance parcourue est alors de 420 kilomètres.

Rechercher des exercices regoupés par thème

exercices compatibles programme 2012 :

indifférent :

[ Accueil ]

Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.