contrôle du 15 décembre 2014

Corrigé de l'exercice 2 (spécialité)

On considère le graphe Γ ci-dessous.

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}{cccccccc}0& 1& 0& 0& 0& 1& 1& 0\\ 1& 0& 1& 0& 1& 1& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 1& 0& 1\\ 1& 1& 0& 0& 1& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 1& 1& 0\end{array}\right)$.

   ---

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

   1. Déterminer, en justifiant, le nombre de chaînes de longueur 3 reliant B à H. Les citer toutes.

      Le terme de la matrice $M^3$ situé à l'intersection de la deuxième ligne et de la dernière colonne est égal à 4. Il existe quatre chaînes de longueur 3 entre les sommets B et H : B-A-F-H, B-A-G-H, B-E-F-H et B-F-E-H.

      ---

   2. Quelle est la distance entre les sommets B et G ?

      La distance de entre les sommets B et G, est la longueur d'une plus courte chaîne de Γ reliant B à G.
      D'après la matrice $M^2$, il existe une chaîne de longueur 2 entre B et G.

      La distance de entre les sommets B et G est égale à 2.

      ---

   3. Quel est le diamètre du graphe Γ ?

   Soit D la matrice qui donne les distances entre deux sommets du graphe :

   Les termes non nuls de la matrice M permettent de compléter D avec $$d=1$$

   $\left(\begin{array}{cccccccc}0& 1& \infty & \infty & \infty & 1& 1& \infty \\ 1& 0& 1& \infty & 1& 1& \infty & \infty \\ \infty & 1& 0& 1& \infty & \infty & \infty & \infty \\ \infty & \infty & 1& 0& 1& \infty & \infty & \infty \\ \infty & 1& \infty & 1& 0& 1& \infty & 1\\ 1& 1& \infty & \infty & 1& 0& \infty & 1\\ 1& \infty & \infty & \infty & \infty & \infty & 0& 1\\ \infty & \infty & \infty & \infty & 1& 1& 1& 0\end{array}\right)$

   Les termes non nuls de la matrice $M^2$ permettent de compléter D avec $$d=2$$

   $\left(\begin{array}{cccccccc}0& 1& 2& \infty & 2& 1& 1& 2\\ 1& 0& 1& 2& 1& 1& 2& 2\\ 2& 1& 0& 1& 2& 2& \infty & \infty \\ \infty & 2& 1& 0& 1& 2& \infty & 2\\ 2& 1& 2& 1& 0& 1& 2& 1\\ 1& 1& 2& 2& 1& 0& 2& 1\\ 1& 2& \infty & \infty & 2& 2& 0& 1\\ 2& 2& \infty & 2& 1& 1& 1& 0\end{array}\right)$

   Les termes non nuls de la matrice $M^3$ permettent de compléter D avec $$d=3$$

   $\left(\begin{array}{cccccccc}0& 1& 2& 3& 2& 1& 1& 2\\ 1& 0& 1& 2& 1& 1& 2& 2\\ 2& 1& 0& 1& 2& 2& 3& 3\\ 3& 2& 1& 0& 1& 2& 3& 2\\ 2& 1& 2& 1& 0& 1& 2& 1\\ 1& 1& 2& 2& 1& 0& 2& 1\\ 1& 2& 3& 3& 2& 2& 0& 1\\ 2& 2& 3& 2& 1& 1& 1& 0\end{array}\right)$

   ---

   La plus grande distance entre deux sommets est 3 donc le diamètre du graphe est 3.

   ---

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

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

      ---

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

      Le diamètre du graphe est égal à 3 par conséquent, pour toute paire de sommets distincts, il existe au moins une chaîne de longueur inférieure ou égale à 3 ayant pour extrémités ces deux sommets.

      Pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe Γ est connexe.

      ---

4. Le graphe Γ modélise le plan d'un parc. Les arêtes du graphe représentent les allées du parc et les sommets du graphe sont les intersections.
   En fin de journée, un agent du service d'entretien fait le tour du parc pour nettoyer les allées.

   1. Est-il possible de planifier un parcours pour que cet agent passe par toutes les allées sans emprunter plusieurs fois la même allée ? Justifier la réponse. Si oui proposer un parcours.

      Organiser la tournée en passant par toutes les allées du parc sans emprunter plusieurs fois la même allée c'est chercher si il existe une chaîne eulérienne.

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

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

      Il est possible d'organiser un parcours qui passe par toutes les allées du parc sans emprunter plusieurs fois la même allée. Par exemple A-B-E-D-C-B-F-E-H-F-A-G-H.

      ---

      ---

   2. Pour rationaliser le nettoyage des allées, on souhaite établir un circuit commençant et finissant par l'entrée du parc G 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 les intersections A 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.