sujet : Centres Étrangers 2014

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

partie a

1. 1. Déterminer en justifiant si le graphe 𝒢 est complet.

      Les sommets A et E ne sont pas adjacents donc le graphe 𝒢 n'est pas complet.

      ---

   2. Déterminer en justifiant si le graphe 𝒢 est connexe.

      La chaîne F - D - E - B - A - C - H - I - G 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.

      ---

2. 1. Donner le degré de chacun des sommets du graphe 𝒢.

      Sommet du graphe 𝒢	A	B	C	D	E	F	G	H	I
      Degré	4	5	4	4	2	2	3	4	2

   2. Déterminer en justifiant si le graphe 𝒢 admet un cycle eulérien ou une chaîne eulérienne.

      Le graphe est connexe et il n'y a que deux sommets B et G de degré impair, il existe donc une chaîne eulérienne d'extrémités B et G.

      ---

3. 1. Donner la matrice M associée au graphe 𝒢 (les sommets seront rangés dans l'ordre alphabétique).

      la matrice d'adjacence du graphe est $M=\left(\begin{array}{ccccccccc}0& 1& 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 1& 1& 1& 1& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 1& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 1& 1\\ 1& 0& 1& 0& 0& 0& 1& 0& 1\\ 0& 0& 0& 0& 0& 0& 1& 1& 0\end{array}\right)$

      ---

   2. On donne : $M^2=\left(\begin{array}{ccccccccc}4& 2& 2& 1& 2& 2& 2& 1& 1\\ 2& 5& 1& 3& 1& 1& 1& 2& 0\\ 2& 1& 4& 2& 1& 1& 1& 2& 2\\ 1& 3& 2& 4& 1& 1& 0& 1& 0\\ 2& 1& 1& 1& 2& 2& 0& 0& 0\\ 2& 1& 1& 1& 2& 2& 0& 0& 0\\ 2& 1& 1& 0& 0& 0& 3& 2& 1\\ 1& 2& 2& 1& 0& 0& 2& 4& 1\\ 1& 0& 2& 0& 0& 0& 1& 1& 2\end{array}\right)$
      Montrer, par le calcul, que le coefficient de la septième ligne et quatrième colonne de la matrice $M^3$ est égal à 3.

      $M^3=M^2\times M$ par conséquent le coefficient de la septième ligne et quatrième colonne de la matrice $M^3$ s'obtient en effectuant le produit matriciel de la septième ligne de la matrice $M^2$ par la quatrième colonne de la matrice M : $$\left(\begin{array}{ccccccccc}2& 1& 1& 0& 0& 0& 3& 2& 1\end{array}\right)\times \left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 1\\ 1\\ 0\\ 0\\ 0\end{array}\right)=2\times 1+1\times 1+1\times 0+0\times 0+0\times 1+0\times 1+3\times 0+2\times 0+1\times 0=3$$

partie b

1. Le graphe 𝒢 donné en partie A modélise cette situation. Recopier et compléter le tableau suivant :

   • Le sommet B de plus haut degré est associé au hall 1

   • Le deuxième sommet G de degré impair est associé au bâtiment 1

   • Le sommet I de degré 2 adjacent à G est associé au bâtiment 2

   • Le sommet H de degré 4 adjacent à G et à I est associé à la vie scolaire et infirmerie

   • Le sommet C de degré 4 adjacent à G est associé au hall 2

   • Le sommet A de degré 4 adjacent à B et C est associé à administration

   • Le sommet D de degré 4 adjacent à B et A est associé à salle des professeurs

   • Les sommets E et F de degré 2 adjacents à B et D peuvent être associés indifféremment à la cantine ou au cdi

   Sommet du graphe 𝒢	A	B	C	D	E	F	G	H	I
   Lieu correspondant dans le lycée	administration	hall 1	hall 2	salle des professeurs	cdi ou cantine	cantine ou cdi	bâtiment 1	vie scolaire et infirmerie	bâtiment 2

   ---

2. Un élève a cours de mathématiques dans le bâtiment 1. À la fin du cours, il doit rejoindre la salle des professeurs pour un rendez vous avec ses parents.
   Déterminer le nombre de chemins en trois étapes permettant à l'élève de rejoindre ses parents puis indiquer quels sont ces chemins.

   Il existe trois chaînes de longueur 3 entre les sommets G et D

   Il existe trois chemins qui permettent en trois étapes de relier le bâtiment 1 à la salle des professeurs : bâtiment 1 - vie scolaire - administration - salle des professeurs ; bâtiment 1 - hall 2 - administration - salle des professeurs ; bâtiment 1 - hall 2 - hall 1 - salle des professeurs.

   ---

3. Le lycée organise une journée portes-ouvertes.

   1. Déterminer, en justifiant, s'il est possible de visiter le lycée en empruntant une seule fois chaque passage entre les différents lieux.

      Le graphe 𝒢 admet une chaîne eulérienne par conséquent, un tel parcours est possible en partant du hall 1 ou du bâtiment 1.

      ---

   2. Sur les arêtes du graphe 𝒢 sont indiqués les temps de parcours exprimés en seconde entre deux endroits du lycée.
      Déterminer, à l'aide de l'algorithme de Dijkstra, le chemin permettant de relier le sommet G au sommet D en un temps minimal. Déterminer ce temps minimal, exprimé en seconde.

      G	A	B	C	E	F	H	I	D	Sommet sélectionné
      0	∞	∞	∞	∞	∞	∞	∞	∞	G (0)
      	∞	∞	90 (A)	∞	∞	40 (G)	20 (G)	∞	I (20)
      	∞	∞	90 (A)	∞	∞	40 (G)		∞	H (40)
      	100 (H)	∞	65 (H)	∞	∞			∞	C (65)
      	100 (H)	95 (C)		∞	∞			∞	B (95)
      	100 (H)			145 (B)	130 (B)			175 (B)	A (100)
      				145 (B)	130 (B)			170 (A)	F (130)
      				145 (B)				165 (F)	E (145)
      								165 (F)	D (165)

      ---

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

      Le trajet qui relie le sommet G au sommet D en un temps minimal est G - H - C - B - F - D. La durée de ce parcours est de 165 secondes.

      ---

---

Rechercher des exercices regoupés par thème

exercices compatibles programme 2012 : ------- Liste des thèmes disponibles -------SuitesFonctions : Lectures graphiquesFonction logarithmeFonction logarithme avec intégraleFonction exponentielleFonction exponentielle avec intégraleCalcul intégralFonctions : Applications économiquesExponentielle : Applications économiquesQuestions ouvertesProbabilitésVariables aléatoires discrètesLoi binomialeLois de probabilité à densitéQCM AnalyseQ.C.M. ProbabilitésQ.C.M. DiversVrai - FauxGraphesGraphes probabilistesGraphes probabilistes et graphesVrai-Faux (spécialité)

indifférent : ------- Liste des thèmes disponibles -------SuitesFonctions : Lectures graphiquesFonctions : Lectures de tableauxFonction logarithmeFonction logarithme avec intégraleFonction exponentielleFonction exponentielle avec intégraleCalcul intégralFonctions : Applications économiquesExponentielle : Applications économiquesAjustement affine d'un nuage de pointsAjustement non affine d'un nuage de pointsAjustement exponentiel d'un nuage de pointsQuestions ouvertesProbabilitésAdéquation à une loi équirépartieVariables aléatoires discrètesLoi binomialeLois de probabilité à densitéQCM AnalyseQ.C.M. ProbabilitésQ.C.M. DiversVrai - FauxVrai - Faux (Probabilités)Réstitution organisée de connaissancesGéométrie dans l'espaceFonctions de deux variablesGraphesGraphes probabilistesGraphes probabilistes et graphesQ.C.M. SpécialitéVrai-Faux (spécialité)

---

[ 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.