bac blanc du 21 février 2008

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

Les questions 1, 2 et 3 sont indépendantes. Toutes les réponses devront être justifiées.

1. La municipalité décide de planter des arbres dans chaque zone, de manière à ce que dans deux zones, reliées entre elles par une voie d'accès principale les espèces plantées soient d'essence différente. Pour des raisons d'entretien, il est préférable que le nombre d'essences plantées soit le plus petit possible.
   On note V le nombre de variétés d'arbres qu'il faut utiliser.

   1. Donner un encadrement de V.

      V est le nombre chromatique du graphe.

      Les degrés des différents sommets sont :

      Sommet	A	B	C	D	E	F	G	H	P
      Degré	3	3	4	4	2	2	4	2	4

      Le plus haut degré des sommets est 4 donc $V⩽5$.

      D'autre part, $\left\{A;P;C\right\}$ est un sous graphe complet d'ordre 3 donc $V⩾3$.

      Ainsi, l'encadrement du nombre chromatique V du graphe est : $3⩽V⩽5$

      ---

   2. Quel nombre minimal d'essences différentes faudra-t-il planter ?

      Une coloration à l'aide de trois couleurs est possible donc le nombre chromatique du graphe est égal à 3.

      ---

      Trois essences d'arbres différentes seront nécéssaire.

      ---

      Remarque

      Dans ce cas, l'algorithme de Welsh et Powell donne une coloration avec 4 couleurs. Pour ceux qui n'ont pas trouvé une coloration avec trois couleurs, la conclusion est :
      "La coloration obtenue à l'aide de l'algorithme de Welsh et Powell donne 4 essences différentes, mais comme $V⩾3$, il existe peut être une possibilité avec 3 essences différentes."

      ---

2. Pour sa campagne électorale, un candidat  souhaite parcourir toutes les voies d'accès principales de ce quartier  sans emprunter plusieurs fois la même voie.

   1. Montrer qu'un tel parcours est possible.

      Parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie c'est chercher l'existence d'une chaîne eulérienne.

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

      • D'autre part, les sommets A et B sont les seuls sommets de degré impair.

      Le graphe est connexe et il y a exactement deux sommets de degré impair donc il existe une chaîne eulérienne.

      ---

   2. Un tel parcours est-il possible pour ce candidat en partant de sa permanence électorale située en P ? si oui le donner, sinon proposer un parcours possible en partant d'un autre endroit.

      Les sommets de degré impair A et B sont les extrémités de la chaîne eulérienne. Il n'est donc pas possible d'effectuer ce parcours en partant de P.

      Exemple d'un parcours possible en partant de B : B - D - F - G - H - E - C - G - D - P - C - A - P - B - A

      ---

3. Un candidat aux élections municipales se trouve dans sa permanence située en zone P quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone H.

   1. Quel est le nombre minimal de voies d'accès principales que ce candidat devra emprunter pour arriver à son rendez-vous ?

      Le nombre minimal de voies d'accès principales que ce candidat devra emprunter pour arriver à son rendez-vous est la distance entre les sommets P et H.

      Les sommets étant classés dans l'ordre alphabétique, la matrice d'adjacence M du graphe est :$$M=\left(\begin{array}{ccccccccc}0& 1& 1& 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 1& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0& 1& 1& 0& 1\\ 0& 0& 1& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1& 0& 1& 0& 0\\ 1& 1& 1& 1& 0& 0& 0& 0& 0\end{array}\right)$$

      La distance entre les sommets P et H est le plus petit entier n tel que le terme $m_{9,8}$ ( ou $m_{8,9}$ le graphe n'étant pas orienté la matrice est symétrique.) de la matrice $M^n$ soit non nul.

      Avec la calculatrice, on trouve $M^2=\left(\begin{array}{ccccccccc}3& 1& 1& 2& 1& 0& 1& 0& 2\\ 1& 3& 2& 1& 0& 1& 1& 0& 2\\ 1& 2& 4& 2& 0& 1& 0& 2& 1\\ 2& 1& 2& 4& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 2& 0& 2& 0& 1\\ 0& 1& 1& 1& 0& 2& 1& 1& 1\\ 1& 1& 0& 1& 2& 1& 4& 0& 2\\ 0& 0& 2& 1& 0& 1& 0& 2& 0\\ 2& 2& 1& 1& 1& 1& 2& 0& 4\end{array}\right)$ et $M^3=\left(\begin{array}{ccccccccc}4& 7& 7& 4& 1& 3& 3& 2& 7\\ 7& 4& 4& 7& 2& 2& 4& 1& 7\\ 7& 4& 2& 4& 6& 2& 9& 0& 9\\ 4& 7& 4& 4& 3& 5& 8& 1& 9\\ 1& 2& 6& 3& 0& 2& 0& 4& 1\\ 3& 2& 2& 5& 2& 2& 5& 1& 3\\ 3& 4& 9& 8& 0& 5& 2& 6& 3\\ 2& 1& 0& 1& 4& 1& 6& 0& 3\\ 7& 7& 9& 9& 1& 3& 3& 3& 6\end{array}\right)$

      C'est dans la matrice $M^3$ que $m_{9,8}\ne 0$ donc, la distance entre les sommets P et H est égale à 3.

      Pour arriver à son rendez-vous, ce candidat devra emprunter au moins trois voies d'accès principales.

      ---

   2. Le graphe pondéré ci-dessous donne, en minutes, les durées moyennes des trajets existants entre les différents lieux.
      En précisant la méthode utilisée, déterminer le plus court chemin que ce candidat devra emprunter pour arriver à son rendez-vous. Combien de temps faut-il prévoir pour effectuer ce trajet ?

      Pour déterminer le plus court chemin possible pour aller de P à H, on utilise l'algorithme de Dijkstra.

      A	B	C	D	E	F	G	H	P	Sommet sélectionné
      ∞	∞	∞	∞	∞	∞	∞	∞	0	P (0)
      4 (A)	6 (P)	11(P)	12(p)	∞	∞	∞	∞		A (4)
      	6(P)	11 (P)	12(p)	∞	∞	∞	∞		B (6)
      		11(P)	10(B)	∞	∞	∞	∞		D (10)
      		11(P)		∞	15(D)	19 (D)	∞		C (11)
      				22(C)	15(D)	19 (D)	∞		F (15)
      				22(C)		19 (D)	∞		G (19)
      				22(C)			29 (G)		E (22)
      							29 (G)		H (29)

      ---

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

      Le trajet le plus court possible pour aller de P à H est P-B-D-G-H. Il faudra prévoir environ 29  minutes pour effectuer ce trajet.

      ---

---

Rechercher des exercices regoupés par thème

exercices compatibles programme 2012 : ------- Liste des thèmes disponibles -------SuitesFonctions (I) : Dérivées, variationFonctions (I) : Lectures graphiquesFonctions (I) : Applications en ÉconomieFonctions (I) : Valeur intermédiaireFonctions (I) : Q.C.MConvexité, point d'inflexionLogarithme népérien : Propriétés algébriquesLogarithme népérien : ÉquationsLogarithme népérien : Équations avec exponentielleFonction logarithmePropriétés des fonctions exponentielleFonction exponentielleExponentielle d'une fonctionPrimitives d'une fonctionCalcul intégralIntégrale et aireFonctions (II) : Applications en ÉconomieFonctions (II) : Q.C.MFonctions : Vrai-FauxProbabilitésLoi binomialeLois de probabilité à densitéQ.C.M ProbabilitésGraphesGraphes probabilistesMatricesVrai - Faux (divers)

indifférent : ------- Liste des thèmes disponibles -------SuitesFonctions (I) : Dérivées, variationFonctions (I) : Étude de fonctions, limites et dérivéeFonctions (I) : Lectures graphiquesFonctions (I) : Applications en ÉconomieFonctions (I) : Valeur intermédiaireFonctions (I) : Q.C.MFonctions (I) : Limites, dérivée de fonctions composéesConvexité, point d'inflexionLogarithme népérien : Propriétés algébriquesLogarithme népérien : ÉquationsLogarithme népérien : Équations avec exponentielleFonction logarithmeLogarithme d'une fonctionPropriétés des fonctions exponentielleFonction exponentielleExponentielle d'une fonctionPrimitives d'une fonctionCalcul intégralIntégrale et aireFonctions (II) : Applications en ÉconomieFonctions (II) : Q.C.MFonctions : Vrai-FauxAjustement affine d'un nuage de pointsAjustement d'un nuage de pointsProbabilitésLoi binomialeLois de probabilité à densitéQ.C.M ProbabilitésGéométrie dans l'espaceFonctions de deux variablesGraphesGraphes probabilistesMatricesVrai - Faux (divers)

---

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