bac blanc du 08 avril 2014

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

1. On appelle M la matrice associée à ce graphe, les sommets étant pris dans l'ordre alphabétique. Une des trois matrices R, S ou T est la matrice $M^3$.
   $R=\left(\begin{array}{ccccccc}4& 2& 2& 3& 3& 4& 1\\ 2& 4& 2& 3& 1& 1& 3\\ 2& 2& 3& 2& 2& 0& 2\\ 3& 3& 2& 5& 2& 2& 2\\ 3& 1& 2& 2& 4& 1& 2\\ 1& 1& 0& 2& 1& 2& 1\\ 1& 4& 2& 2& 2& 1& 4\end{array}\right)$ $S=\left(\begin{array}{rrrrrrr}8& 12& 9& 12& 7& 4& 11\\ 12& 8& 9& 12& 11& 4& 7\\ 9& 9& 6& 11& 6& 4& 6\\ 12& 12& 11& 12& 12& 4& 12\\ 7& 11& 6& 12& 6& 6& 10\\ 4& 4& 4& 4& 6& 2& 6\\ 11& 7& 6& 12& 10& 6& 6\end{array}\right)$ $T=\left(\begin{array}{ccccccc}4& 1& 2& 2& 3& 4& 1\\ 2& 4& 2& 3& 1& 2& 3\\ 1& 2& 3& 2& 2& 1& 2\\ 3& 3& 2& 6& 3& 2& 3\\ 2& 1& 2& 3& 4& 2& 2\\ 2& 2& 1& 2& 2& 3& 2\\ 2& 3& 2& 3& 2& 2& 4\end{array}\right)$
   Sans calculer la matrice $M^3$, indiquer quelle est la matrice $M^3$ en justifiant votre choix.

   Les sommets étant classés dans l'odre alphabétique, les termes de la matrice $M^3$ donnent le nombre de chaînes de longueur 3 reliant deux sommets quelconques.

   • Le graphe n'est pas orienté et la matrice T n'est pas symétrique par conséquent, la matrice T ne convient pas.

   • Il existe au moins une chaîne de longueur 3 qui relie les sommets C et F par exemple C-B-E-F or $$$r_{3,6}=0$ et $r_{6,3}=0$ donc la matrice R ne convient pas.

   La matrice S est la seule des trois matrices proposées susceptible d'être égale à $M^3$

   ---

2. Ce graphe est-il complet ? Ce graphe est-il connexe ?

   • Le graphe est d'ordre 7 et aucun des sommet n'est de degré 6 donc le graphe n'est pas complet.

     ---

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

     ---

3. Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne.

   Déterminons le degré de chacun des sommets.

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

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

   ---

4. Un représentant, a modélisé à l'aide du graphe ci-dessous le réseau routier reliant différents clients notés A, B, C, D, E, F et G. Les arêtes sont pondérés par les distances en kilomètre à parcourir.

   Après avoir visité le client C, ce représentant souhaite se rendre chez le client D.

   1. En précisant la méthode utilisée, déterminer le trajet le plus court (en kilomètres) pour aller de C à D. Préciser la longueur en kilomètres de ce trajet.

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

      A	B	C	D	E	F	G	Sommet sélectionné
      ∞	∞	0	∞	∞	∞	∞	C (0)
      35 (C)	6 (C)		43 (C)	∞	∞	∞	B (6)
      35 (C)			43 (C)	14 (B)	∞	∞	E (14)
      35 (C)			43 (C)		20 (E)	25 (E)	F (20)
      35 (C)			43 (C)			25 (E)	G (25)
      33 (G)			43 (C)				A (33)
      			42 (A)				D (42)

      ---

      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 A\leftarrow G\leftarrow E\leftarrow B\leftarrow C$.

      Le trajet le plus court possible pour aller de C à D est C-B-E-G-A-D. La distance parcourue est de 42 km.

      ---

   2. Existe-t-il un parcours de même distance permettant à ce représentant de visiter tous ses clients ?

      Le parcours obtenu à l'aide de l'algorithme de Dijkstra ne permet pas au représentant de visiter le client F or la chaîne E-F-G a un poids égal à celui de l'arête E-G

      Le trajet C-B-E-F-G-A-D permet au représentant de visiter tous ses clients en parcourant la même distance de 42 km.

      ---

---

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.