contrôles en terminale ES

bac blanc du 24 février 2017

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

On considère le graphe ci-dessous :

Donner l'ordre du graphe puis le degré de chacun des sommets.
- Il y a 10 sommets donc le graphe est d'ordre 10.
- Les degrés des sommets sont :
  Sommets A B C D E F G H I J
  Degré 3 4 2 4 4 4 4 3 2 2
Recopier et compléter la matrice d'adjacence M associée au graphe, les sommets étant rangés dans l'ordre alphabétique.
La matrice d'adjacence associée au graphe est $M = (\begin{matrix} 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix})$ .
On donne les matrices $M^{2} = (\begin{matrix} 3 & 0 & 2 & 0 & 1 & 2 & 1 & 0 & 1 & 0 \\ 0 & 4 & 0 & 3 & 2 & 1 & 1 & 1 & 0 & 1 \\ 2 & 0 & 2 & 0 & 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 4 & 1 & 1 & 2 & 1 & 0 & 1 \\ 1 & 2 & 1 & 1 & 4 & 2 & 2 & 1 & 1 & 0 \\ 2 & 1 & 2 & 1 & 2 & 4 & 2 & 2 & 0 & 0 \\ 1 & 1 & 1 & 2 & 2 & 2 & 4 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 2 & 1 & 3 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 2 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 2 \end{matrix})$ et $M^{3} = (\begin{array}{r} 0 & 8 & 0 & 8 & 3 & 2 & 3 & 3 & 0 & 4 \\ 8 & 2 & 7 & 3 & 6 & 10 & 8 & 3 & 2 & 0 \\ 0 & 7 & 0 & 7 & 3 & 2 & 3 & 2 & 0 & 2 \\ 8 & 3 & 7 & 2 & 8 & 10 & 6 & 3 & 2 & 0 \\ 3 & 6 & 3 & 8 & 6 & 9 & 9 & 7 & 1 & 2 \\ 2 & 10 & 2 & 10 & 9 & 6 & 9 & 4 & 2 & 2 \\ 3 & 8 & 3 & 6 & 9 & 9 & 6 & 7 & 1 & 2 \\ 3 & 3 & 2 & 3 & 7 & 4 & 7 & 2 & 4 & 0 \\ 0 & 2 & 0 & 2 & 1 & 2 & 1 & 4 & 0 & 3 \\ 4 & 0 & 2 & 0 & 2 & 2 & 2 & 0 & 3 & 0 \end{array})$
1. Donner, en justifiant, le nombre de chaînes de longueur 3 reliant A à E. Les citer toutes.
  Les sommets étant classés dans l'odre alphabétique, le terme de $a_{0, 5} = 3$ de la matrice $M^{3}$ donne le nombre de chaînes de longueur 3 reliant le sommet A au sommet E.
  Il existe trois chaînes de longueur 3 qui relient les sommets A et E : A-B-F-E ; A-B-G-E et A-D-F-E.
2. Effectuer le produit de la troisième ligne de la matrice $M^{2}$ et de la septième colonne de la matrice $M^{3}$ . Interpréter le résultat.
  $(\begin{matrix} 2 & 0 & 2 & 0 & 1 & 2 & 1 & 0 & 0 & 0 \end{matrix}) \times (\begin{matrix} 3 \\ 8 \\ 3 \\ 6 \\ 9 \\ 9 \\ 6 \\ 7 \\ 1 \\ 2 \end{matrix}) = (\begin{matrix} 2 \times 3 + 0 \times 8 + 2 \times 3 + 0 \times 6 + 1 \times 9 + 2 \times 9 + 1 \times 6 + 0 \times 7 + 0 \times 1 + 0 \times 2 \end{matrix}) = (\begin{matrix} 45 \end{matrix})$
  Le produit de la troisième ligne de la matrice $M^{2}$ et de la septième colonne de la matrice $M^{3}$ est égal à 45. C'est le terme de $m_{3, 7} = 45$ de la matrice $M^{5}$ .
  Il y a donc 45 chaînes de longueur 5 entre les sommets C et G.
Déterminer en justifiant si ce graphe est :
1. complet ;
  Les sommets A et C ne sont pas adjacents donc le graphe n'est pas complet.
2. connexe.
  La chaîne A-B-C-D-E-F-G-H-I-J contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne de longueur 9 les reliant donc le graphe est connexe.
Ce graphe modélise le plan d'un parc public. Les arêtes du graphe représentent les allées du parc et les sommets du graphe sont les intersections.
1. En début de journée, le responsable du service d'entretien fait le tour du parc pour inspecter l'état des allées.
  Est-il possible d'optimiser le parcours pour que le responsable passe par toutes les allées sans emprunter plusieurs fois la même allée ? Justifier la réponse. Si oui proposer un parcours.
  Effectuer un parcours qui passe une seule fois par chaque allée c'est chercher si il existe une chaîne eulérienne.
  Le graphe est connexe et il n'y a que deux sommets A et H de degré impair, il existe donc des chaînes eulérienne d'extrémités A et H.
  Un parcours qui passe une seule fois par chaque allée est possible par exemple A - B - C - D - E - F - D - A - J - I - H - G - B - F - G - E - H.
2. Pour rationaliser le nettoyage des allées, on souhaite établir un circuit commençant et finissant par l'entrepôt situé en E et qui passe par toutes les allées une et une seule fois.
  Quel est le nombre minimal d'allées qu'il faudrait tracer pour obtenir un tel circuit ?
  Pour qu'un graphe connexe admette un cycle eulérien, il suffit que tous ses sommets soient de degré pair.
  Il suffit de rajouter une allée entre A et H pour qu'un tel circuit soit possible.

Rechercher des exercices regoupés par thème

exercices compatibles programme 2012 :

indifférent :

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	H	I	J
Degré	3	4	2	4	4	4	4	3	2	2