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

sujet : Asie 2013

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

Les deux parties de l'exercice sont indépendantes.

partie a

Pour accéder à sa messagerie, Antoine a choisi un code qui doit être reconnu par le graphe étiqueté suivant, de sommets 1, 2, 3 et 4 :

Une succession des lettres constitue un code possible si ces lettres se succèdent sur un chemin du graphe orienté ci-dessus, en partant du sommet 1 et en sortant au sommet 4. Les codes SES et SPPCES sont ainsi des codes possibles, contrairement aux codes SUN et SPEN.

Parmi les trois codes suivants, écrire sur votre copie le (ou les) code(s) reconnu(s) par le graphe : SUCCÈS ; SCENES ; SUSPENS.
SUSPENS est un code reconnu par le graphe
Recopier et compléter la matrice d'adjacence A associée au graphe. On prendra les sommets dans l'ordre 1-2-3-4. $A = (\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ \dots & \dots & \dots & \dots \\ \dots & \dots & \dots & \dots \end{matrix})$
La matrice d'adjacence associée au graphe est $A = (\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix})$
Avec une calculatrice on a calculé : $A^{4} = (\begin{matrix} 5 & 12 & 8 & 3 \\ 12 & 29 & 20 & 8 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{matrix})$ . En déduire le nombre de codes de 4 lettres reconnus par le graphe. Quels sont ces codes ?
Le coefficient situé à l'intersection de la première ligne et de la quatrième colonne de la matrice $A^{4}$ est égal à 3. Il existe donc 3 chaînes de longueur 4 partant du sommet 1 et sortant au sommet 4.
Il y a 3 codes de 4 lettres reconnus par le graphe : SPES, SCES et SENS.

partie b

Antoine décide d'aller visiter neuf châteaux de la Loire. Il a construit le graphe ci-dessus où les sommets représentent :

A : Amboise	B : Blois	C : Cheverny	D : Chambord	E : Chenonceau
T : Tours	V : Villandry	R : Azay-le-Rideau	N : Chinon

Sur les arêtes sont indiquées les distances en km

Antoine peut-il partir de Blois et y revenir, en parcourant une et une seule fois chacune des routes matérialisées par les arêtes de ce graphe ? On justifiera la réponse.
La chaîne N - V - T - B - D - C - E - R - A contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Le graphe est connexe et les sommets du graphe sont tous de degré pair, il existe donc un cycle eulérien. Antoine peut partir de Blois et y revenir, en parcourant une et une seule fois chacune des routes matérialisées par les arêtes de ce graphe.

Déterminer le plus court chemin pour aller du château de Chambord au château de Chinon. On donnera le parcours ainsi que le nombre total de kilomètres.

À l'aide de l'algorithme de Dijkstra, déterminons le plus court chemin pour aller du château de Chambord au château de Chinon.

D	A	B	C	E	T	R	V	N	Sommet sélectionné
0	∞	∞	∞	∞	∞	∞	∞	∞	D (0)
	∞	19 (D)	18 (D)	∞	∞	∞	∞	∞	C (18)
	∞	19 (D)		56 (C)	∞	∞	∞	∞	B (19)
	54 (B)			56 (C)	82 (B)	∞	∞	∞	A (54)
				56 (C)	79 (A)	112 (A)	∞	∞	E (56)
					79 (A)	109 (E)	∞	∞	T (79)
						103 (T)	95 (T)	∞	V (95)
						103 (T)		127(V)	R (103)
								124 (R)	N (124)

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

Le plus court chemin pour aller du château de Chambord au château de Chinon est : Chambord ; Blois ; Amboise ; Tours ; Azay-le-Rideau ; Chinon. La distance parcourue est de 124 km.

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.