contrôle du 23 janvier 2018

Corrigé de l'exercice 1

1. Donner l'ordre du graphe puis le degré de chacun des sommets.

   • Il y a 8 sommets donc le graphe Γ est d'ordre 8.

     ---

   • Les degrés des sommets sont :

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

2. On range les sommets par ordre alphabétique. Compléter la matrice d'adjacence M associée au graphe.

   La matrice d'adjacence M associée au graphe : $M=\left(\begin{array}{cccccccc}0& 1& 0& 0& 1& 0& 1& 1\\ 1& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 1& 0& 1\\ \mathbf{1}& \mathbf{0}& \mathbf{0}& \mathbf{1}& \mathbf{0}& \mathbf{1}& \mathbf{1}& \mathbf{0}\\ \mathbf{0}& \mathbf{0}& \mathbf{0}& \mathbf{1}& \mathbf{1}& \mathbf{0}& \mathbf{1}& \mathbf{0}\\ 1& 0& 0& 0& 1& 1& 0& 1\\ 1& 0& 0& 1& 0& 0& 1& 0\end{array}\right)$.

   ---

3. On donne les matrices $M^2=\left(\begin{array}{cccccccc}4& 0& 1& 2& 1& 2& 2& 1\\ 0& 2& 0& 1& 1& 0& 1& 1\\ 1& 0& 2& 0& 1& 1& 0& 1\\ 2& 1& 0& 4& 1& 1& 3& 0\\ 1& 1& 1& 1& 4& 2& 2& 3\\ 2& 0& 1& 1& 2& 3& 1& 2\\ 2& 1& 0& 3& 2& 1& 4& 1\\ 1& 1& 1& 0& 3& 2& 1& 3\end{array}\right)$ et $M^3=\left(\begin{array}{rrrrrrrr}4& 5& 2& 5& 10& 5& 8& 8\\ 5& 0& 3& 2& 2& \cdots & 2& 2\\ 2& 3& 0& 5& 2& 1& 4& 1\\ 5& 2& 5& 2& 10& 8& 4& 9\\ 10& 2& 2& 10& 6& 7& 10& 4\\ 5& 3& 1& 8& 7& 4& 9& 4\\ 8& 2& 4& 4& 10& 9& 6& 9\\ 8& 2& 1& 9& 4& 4& 9& 2\end{array}\right)$

   1. En détaillant le calcul, déterminer le coefficient de la deuxième ligne et sixième colonne de la matrice $M^3$.

      Au choix :

      • $M^3=M\times M^2$, par conséquent, le coefficient $a_{2,6}$ de la deuxième ligne et sixième colonne de la matrice $M^3$ est égal au produit de la deuxième ligne de la matrice M par la sixième colonne de la matrice $M^2$ :$$a_{2,6}=\left(\begin{array}{cccccccc}1& 0& 1& 0& 0& 0& 0& 0\end{array}\right)\times \left(\begin{array}{c}2\\ 0\\ 1\\ 1\\ 2\\ 3\\ 1\\ 2\end{array}\right)=\left(1\times 2+0\times 0+1\times 1+0\times 1+0\times 2+0\times 3+0\times 2+0\times 2\right)=\left(3\right)$$

      • $M^3=M^2\times M$, par conséquent, le coefficient $a_{2,6}$ de la deuxième ligne et sixième colonne de la matrice $M^3$ est égal au produit de la deuxième ligne de la matrice $M^2$ par la sixième colonne de la matrice M :$$a_{2,6}=\left(\begin{array}{cccccccc}0& 2& 0& 1& 1& 0& 1& 1\end{array}\right)\times \left(\begin{array}{c}0\\ 0\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right)=\left(0\times 0+2\times 0+0\times 0+1\times 1+1\times 1+0\times 0+1\times 1+1\times 0\right)=\left(3\right)$$

      Le coefficient de la deuxième ligne et sixième colonne de la matrice $M^3$ est égal à 3.

      ---

   2. Donner, en justifiant, le nombre de chaînes de longueur 3 reliant B à F. Les citer toutes.

      Le coefficient de la deuxième ligne et sixième colonne de la matrice $M^3$ est égal à 3 par conséquent, il y a 3 chaînes de longueur 3 reliant B à F : B - A - E - F ; B - A - G - F et B - C - D - F.

      ---

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

      Les termes de la matrice $M^3$ qui ne sont pas sur la diagonale sont différents de 0. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne de longueur 3 les reliant donc le graphe est connexe.

      ---

5. En justifiant la réponse, dire si ce graphe admet une chaîne eulérienne. Si oui, donner une telle chaîne.

   Le graphe est connexe et il n'y a que deux sommets F et H de degré impair, il existe donc des chaînes eulérienne d'extrémités F et H par exemple : H - D - E - A - G - F - E - G - H - A - B - C - D - F.

   ---

6. Le responsable du parc souhaite réorganiser le nettoyage des allées, par un circuit commençant et finissant par le sommet A et qui passe par toutes les allées une et une seule fois.
   Quel est le nombre minimal d'allées qu'il faudrait ajouter pour obtenir un tel circuit ? Préciser les extrémités.

   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 les sommets F et H pour qu'un tel circuit soit possible.

   ---

---

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.