bac blanc du 01 mars 2011

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

1. Existe-t-il des chaînes de longueur 2 partant du sommet A et aboutissant au sommet C ?

   Soit M la matrice d'adjacence du graphe, les sommets étant pris dans l'ordre alphabétique. $M=\left(\begin{array}{ccccccc}0& 1& 1& 1& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 0& 0& 1& 0& 1\\ 1& 0& 0& 0& 0& 0& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 1& 1& 0& 0& 1& 0& 1\\ 0& 1& 1& 1& 0& 1& 0\end{array}\right)$

   Le nombre de chaînes de longueur 2 partant du sommet A et aboutissant au sommet C est le terme $a_{13}$ situé à l'intersection de la première ligne et de la troisième colonne de la matrice $M^2$. Or $M^2=\left(\begin{array}{ccccccc}4& 1& 0& 0& 3& 1& 4\\ 1& 4& 3& 2& 1& 3& 1\\ 0& 3& 3& 2& 0& 3& 0\\ 0& 2& 2& 2& 0& 2& 0\\ 3& 1& 0& 0& 3& 1& 3\\ 1& 3& 3& 2& 1& 4& 1\\ 4& 1& 0& 0& 3& 1& 4\end{array}\right)$ et $a_{13}=0$

   Il n'existe pas de chaînes de longueur 2 partant du sommet A et aboutissant au sommet C

   ---

2. Le graphe admet-il des chaînes eulériennes ? Si oui, en préciser une.

   La chaîne A-D-G-C-E-B-F contient tous les sommets du graphe par conséquent, il existe au moins une chaîne reliant deux sommets quelconques. Donc le graphe est connexe.

   Déterminons le degré de chacun des sommets.

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

   ---

   Le graphe est connexe et il existe deux sommets de degré impair, il admet donc une chaîne eulérienne commençant par un des deux sommets de degré impair (C ou E) et finissant par le deuxième sommet de degré impair. Par exemple E - F - B - G - D - A - F - G - C - E - B - A - C

   ---

3. 1. Donner un encadrement du nombre chromatique X du graphe.

      Le plus haut degré des sommets est 4 donc $X⩽4+1$ . D'autre part, A-B-F est un sous graphe complet d'ordre 3 donc $X⩾3$.

      Ainsi, $3⩽X⩽5$

      ---

   2. Déterminer ce nombre chromatique, en explicitant clairement la démarche.

      Utilisons l'algorithme de coloration de Welsh et Powell :
      Les sommets étant classés par ordre de degré décroissant, on attribue la couleur 1 aux sommets A, G et E ; la couleur 2 aux sommets B, C et D ; la couleur 3 au sommet F.

      Une coloration du graphe avec 3 couleurs est possible et $3⩽X⩽5$ donc le nombre chromatique de ce graphe est égal à 3.

      ---

4. Le graphe pondéré ci-dessous, donne en minutes, les durées moyennes des parcours de A à C en tenant compte des sens uniques.
   Un automobiliste doit se rendre de A à C. En utilisant un algorithme, déterminer le trajet le plus rapide pour aller de A à C.
   Le retour sera-t-il plus rapide que l'aller ?

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

   A	B	C	D	E	F	G	Sommet sélectionné
   0	∞	∞	∞	∞	∞	∞	A (0)
   	28 (A)	∞	19 (A)	∞	10 (A)	∞	F (10)
   	28 (A)	∞	19 (A)	21 (F)		37 (F)	D (19)
   	28 (A)	∞		21 (F)		37 (F)	E (21)
   	27 (E)	48 (E)				37 (F)	B (27)
   		48 (E)				34 (B)	G (34)
   		42 (G)					C (42)

   ---

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

   Le trajet le plus court possible pour aller de A à G est A-F-E-B-G-C. Il faudra prévoir 42 minutes pour effectuer ce trajet. Le seul retour possible qui dure 38 minutes est plus rapide.

   ---

---

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.