contrôles en terminale ES

contrôle du 08 février 2016

Corrigé de l'exercice 3 : Élèves ayant suivi l'enseignement de spécialité

partie a

On considère le graphe ci-dessous :

Donner la matrice d'adjacence M de ce graphe, les sommets étant pris dans l'ordre alphabétique.
La matrice d'adjacence du graphe est $M = (\begin{matrix} 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \end{matrix})$ .
On donne $M^{2} = (\begin{matrix} 3 & 0 & 3 & 0 & 0 & 1 & 1 \\ 0 & 2 & 0 & 2 & 2 & 0 & 0 \\ 3 & 0 & 3 & 0 & 0 & 1 & 1 \\ 0 & 2 & 0 & 2 & 2 & 0 & 0 \\ 0 & 2 & 0 & 2 & 4 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 2 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 2 \end{matrix})$ et $M^{3} = (\begin{matrix} 0 & 6 & 0 & 6 & 1 & 1 \\ 6 & 0 & 6 & 0 & 0 & 2 & 2 \\ 0 & 6 & 0 & 6 & 8 & 1 & 1 \\ 6 & 0 & 6 & 0 & 0 & 2 & 2 \\ 0 & 8 & 0 & 2 & 5 & 5 \\ 1 & 2 & 1 & 2 & 5 & 2 & 3 \\ 1 & 2 & 1 & 2 & 5 & 3 & 2 \end{matrix})$ .
1. En détaillant le calcul, déterminer le nombre de chaînes de longueur 3 entre les sommets A et E.
  Le nombre de chaînes de longueur 3 entre les sommets A et E est égal au terme $a_{1, 5}$ de la matrice $M^{3}$ situé à l'intersection de la première ligne et de la cinquième colonne.
  Comme $M^{3} = M^{2} \times M$ , on en deduit que $a_{1, 5} = (\begin{matrix} 3 & 0 & 3 & 0 & 0 & 1 & 1 \end{matrix}) \times (\begin{matrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix}) = 3 + 3 + 1 + 1 = 8$
  Il y a 8 chaînes de longueur 3 entre les sommets A et E.
2. Déterminer la matrice D des distances entre les sommets du graphe. En déduire le diamètre du graphe.
  Le graphe n'étant pas orienté, nous pouvons compléter la matrice $M^{3} = (\begin{matrix} 0 & 6 & 0 & 6 & 8 & 1 & 1 \\ 6 & 0 & 6 & 0 & 0 & 2 & 2 \\ 0 & 6 & 0 & 6 & 8 & 1 & 1 \\ 6 & 0 & 6 & 0 & 0 & 2 & 2 \\ 8 & 0 & 8 & 0 & 2 & 5 & 5 \\ 1 & 2 & 1 & 2 & 5 & 2 & 3 \\ 1 & 2 & 1 & 2 & 5 & 3 & 2 \end{matrix})$ .
  La distance entre deux sommets du graphe est la longueur d'une plus courte chaîne entre ces deux sommets.
  Soit D la matrice qui donne les distances entre deux sommets du graphe.
  - Les termes non nuls de la matrice M permettent de compléter D avec la distance $d = 1$ : $(\begin{matrix} 0 & 1 & \infty & 1 & 1 & \infty & \infty \\ 1 & 0 & 1 & \infty & \infty & \infty & \infty \\ \infty & 1 & 0 & 1 & 1 & \infty & \infty \\ 1 & \infty & 1 & 0 & \infty & \infty & \infty \\ 1 & \infty & 1 & \infty & 0 & 1 & 1 \\ \infty & \infty & \infty & \infty & 1 & 0 & 1 \\ \infty & \infty & \infty & \infty & 1 & 1 & 0 \end{matrix})$
  - Les termes non nuls de la matrice $M^{2}$ permettent de compléter D avec une distance $d = 2$ : $(\begin{matrix} 0 & 1 & 2 & 1 & 1 & 2 & 2 \\ 1 & 0 & 1 & 2 & 2 & \infty & \infty \\ 2 & 1 & 0 & 1 & 1 & 2 & 2 \\ 1 & 2 & 1 & 0 & 2 & \infty & \infty \\ 1 & 2 & 1 & 2 & 0 & 1 & 1 \\ 2 & \infty & 2 & \infty & 1 & 0 & 1 \\ 2 & \infty & 2 & \infty & 1 & 1 & 0 \end{matrix})$
  - Les termes non nuls de la matrice $M^{3}$ permettent de compléter D avec une distance $d = 3$ : $(\begin{matrix} 0 & 1 & 2 & 1 & 1 & 2 & 2 \\ 1 & 0 & 1 & 2 & 2 & 3 & 3 \\ 2 & 1 & 0 & 1 & 1 & 2 & 2 \\ 1 & 2 & 1 & 0 & 2 & 3 & 3 \\ 1 & 2 & 1 & 2 & 0 & 1 & 1 \\ 2 & 3 & 2 & 3 & 1 & 0 & 1 \\ 2 & 3 & 2 & 3 & 1 & 1 & 0 \end{matrix})$
  La matrice des distances entre les sommets du graphe est : $D = (\begin{matrix} 0 & 1 & 2 & 1 & 1 & 2 & 2 \\ 1 & 0 & 1 & 2 & 2 & 3 & 3 \\ 2 & 1 & 0 & 1 & 1 & 2 & 2 \\ 1 & 2 & 1 & 0 & 2 & 3 & 3 \\ 1 & 2 & 1 & 2 & 0 & 1 & 1 \\ 2 & 3 & 2 & 3 & 1 & 0 & 1 \\ 2 & 3 & 2 & 3 & 1 & 1 & 0 \end{matrix})$ . Le diamètre du graphe est 3.
Déterminer, en justifiant, si le graphe admet une chaîne eulérienne. Si oui, donner une telle chaîne.
Le diamètre du graphe est égal à 3 par conséquent, pour toute paire de sommets distincts, il existe au moins une chaîne de longueur inférieure ou égale à 3 ayant pour extrémités ces deux sommets. Par conséquent, le graphe est connexe.
Le tableau suivant, donne le degré des sommets du graphe :
Sommets A B C D E F G
Degré 3 2 3 2 4 2 2
Le graphe est connexe et il n'y a que deux sommets A et C de degré impair, il existe donc une chaîne eulérienne d'extrémités A et C. Par exemple A-B-C-D-A-E-F-G-E-C.

partie b

Le graphe ci-dessous, modélise le réseau routier entre un fournisseur F et ses différents clients. Les arêtes sont pondérées par les distances exprimées en kilomètres.
Après avoir effectué une livraison chez le client C, le livreur doit retourner à l'entrepôt du fournisseur.
À l'aide d'un algorithme, déterminer le trajet le plus court pour aller de C à F en précisant la distance parcourue.

Pour déterminer le trajet le plus rapide pour aller de A à G, on utilise l'algorithme de Dijkstra.

A	B	C	D	E	F	G	Sommet sélectionné
∞	∞	0	∞	∞	∞	∞	C (0)
∞	12 (C)		5 (C)	18 (C)	∞	∞	D (5)
13 (D)	12 (C)			18 (C)	∞	∞	B (12)
13 (D)				18 (C)	∞	∞	A (13)
				17 (A)	∞	∞	E (17)
					23 (E)	19 (E)	E (19)
					22 (G)		G (22)

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

Le trajet le plus court possible pour aller de C à F est C-D-A-E-G-F. La distance de ce trajet est de 22 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.

Sommets	A	B	C	D	E	F	G
Degré	3	2	3	2	4	2	2