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

sujet : Liban 2013

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

Le graphe ci-dessous représente les autoroutes entre les principales villes du Sud de la France :
Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Montpellier (P), Brive (R), Toulouse (T), Valence (V) et Biarritz (Z).

Pour cette question, on justifiera chaque réponse.
1. Déterminer l'ordre du graphe.
  Il y a 9 sommets donc l'ordre du graphe est 9.
2. Déterminer si le graphe est connexe.
  La chaîne B-R-C-L-V-M-P-T-Z contient tous les sommets du graphe. Donc le graphe est connexe.
3. Déterminer si le graphe est complet.
  Il n'y a pas d'arête ente les sommets B et C donc le graphe n'est pas complet.
Un touriste atterrit à l'aéroport de Lyon et loue une voiture.
Déterminer, en justifiant, s'il pourra visiter toutes les villes en empruntant une et une seule fois chaque autoroute.
Il y a 4 sommets de degré impair, les sommets B, R, C et V. Donc il n'existe pas de chaîne eulérienne.
Ce n'est pas possible de visiter toutes les villes en empruntant une et une seule fois chaque autoroute.
Il décide finalement d'aller seulement de Lyon à Biarritz.
On note N la matrice associée au graphe, les sommets étant rangés dans l'ordre alphabétique : B, C, L, M, P, R, T, V, Z.
Voici les matrices N et $N^{3}$ : $\begin{matrix} N = (\begin{matrix} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}) & et & N^{3} = (\begin{matrix} 4 & 2 & 1 & 1 & 3 & 6 & 6 & 1 & 5 \\ 2 & 0 & 5 & 2 & 8 & 6 & 1 & 1 & 3 \\ 1 & 5 & 0 & 2 & 1 & 0 & 3 & 5 & 0 \\ 1 & 2 & 2 & 2 & 5 & 2 & 1 & 4 & 1 \\ 3 & 8 & 1 & 5 & 2 & 1 & 8 & 7 & 1 \\ 6 & 6 & 0 & 2 & 1 & 2 & 8 & 3 & 2 \\ 6 & 1 & 3 & 1 & 8 & 8 & 4 & 1 & 6 \\ 1 & 1 & 5 & 4 & 7 & 3 & 1 & 2 & 1 \\ 5 & 3 & 0 & 1 & 1 & 2 & 6 & 1 & 2 \end{matrix}) \end{matrix}$
1. En détaillant le calcul, déterminer le coefficient de la troisième ligne et dernière colonne de la matrice $N^{4}$ .
  $N^{4} = N^{3} \times N$ .
  Le coefficient $a_{3, 9}$ de la troisième ligne et dernière colonne de la matrice $N^{4}$ est égal au produit de la matrice ligne de la troisième ligne de la matrice $N^{3}$ par la matrice colonne de la dernière colonne de la matrice N : $(\begin{matrix} 1 & 5 & 0 & 2 & 1 & 0 & 3 & 5 & 0 \end{matrix}) \times (\begin{matrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}) = 1 \times 1 + 3 \times 1 = 4$
  Le coefficient de la troisième ligne et dernière colonne de la matrice $N^{4}$ est égal à 4.
2. En donner une interprétation.
  Le coefficient $a_{3, 9}$ de la matrice $N^{4}$ donne le nombre de chaînes de longueur 4 reliant les sommets B et Z :
  Il y 4 possibilités d'aller de Lyon à à Biarritz en quatre étapes.

Sur les arêtes du graphe sont maintenant indiqués les prix des péages en euro.

À l'aide de l'algorithme de Dijkstra, déterminer le chemin que doit prendre le touriste pour minimiser le coût des péages de Lyon à Biarritz.

L	B	C	M	P	R	T	V	Z	Sommet sélectionné
0	∞	∞	∞	∞	∞	∞	∞	∞	L (0)
	∞	10,7 (L)	∞	∞	∞	∞	7,1 (L)	∞	V (7,1)
	∞	10,7 (L)	22,8 (V)	23,3 (V)	∞	∞		∞	C (10,7)
	∞		22,8 (V)	19,3 (C)	22,2 (C)	∞		∞	P (19,3)
	∞		22,8 (V)		22,2 (C)	38,9 (P)		∞	R (22,2)
	33,7 (R)		22,8 (V)			36,8 (R)		∞	M (22,8)
	33,7 (R)					36,8 (R)		∞	B (33,7)
						36,8 (R)		38,1 (B)	T (36,8)
								38,1 (B)	Z (38,1)

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

Le chemin qui minimise le coût des péages de Lyon à Biarritz est Lyon(L) - Clermont-Ferrand (C) - Brive (R) - Bordeaux (B)- Biarritz (Z).

Déterminer le coût, en euro, de ce trajet.
Le coût des péages de ce trajet est de 38,1 €.

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.