sujet : Pondichéry 2017

Corrigé de l'exercice 3 : candidats ayant suivi l'enseignement de spécialité ES

1. 1. Quelles caractéristiques du graphe permettent d'affirmer qu'il existe un trajet qui permet à Alexis d'emprunter chaque liaison aérienne une et une seule fois ?

      • La chaîne A - W - C - B - N - M 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.

      • Le graphe étant connexe, déterminons le degré de chacun des sommets :

        Sommets	A	B	C	M	N	W
        Degré	2	2	4	3	3	4

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

      ---

   2. Donner un exemple d'un tel trajet.

      Le trajet N - M - W - C - B - N - W - A - C - M permet à Alexis d'emprunter chaque liaison aérienne une et une seule fois .

      ---

2. Alexis veut relier Boston à Miami. En utilisant un algorithme, déterminer le trajet le moins cher ainsi que le coût de ce trajet.

   À l'aide de l'algorithme de Dijkstra, déterminons le trajet le moins cher pour se rendre de Boston à Miami :

   B	A	C	M	N	W	Sommet sélectionné
   0	∞	∞	∞	∞	∞	B (0)
   	∞	130 (B)	∞	170 (B)	∞	C (130)
   	230 (C)		280 (C)	170 (B)	250 (C)	N (170)
   	230 (C)		280 (C)		250 (C)	A (230)
   			280 (C)		250 (C)	W (250)
   			280 (C)			M (280)

   ---

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

   Le trajet le moins cher pour se rendre de Boston à Miami est Boston, Chicago, Miami pour un coût de 280 dollars.

   ---

3. 1. Donner la matrice d'adjacence P de ce graphe en classant les sommets par ordre alphabétique.

      La matrice d'adjacence P de ce graphe est : $P=\left(\begin{array}{cccccc}0& 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 1\\ 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 1& 1& 0\end{array}\right)$

      ---

   2. Alexis souhaite aller d'Atlanta à Boston en utilisant au maximum trois liaisons aériennes.
      Combien y a-t-il de trajets possibles ? Justifier la démarche puis décrire chacun de ces trajets.

      Pour aller d'Atlanta à Boston en utilisant au maximum trois liaisons aériennes on regarde donc successivement les coefficients de la première ligne (sommet A) et deuxième colonne (sommet B) des matrices P, $P^2$ et $P^3$ :$$\begin{array}{ccccc}P=\left(\begin{array}{cccccc}0& 0& 1& 0& 0& 1\\ 0& 0& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 1\\ 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 1& 1& 0\end{array}\right)& \text{;}& P^2=\left(\begin{array}{cccccc}2& 1& 1& 2& 1& 1\\ 1& 2& 0& 2& 0& 2\\ 1& 0& 4& 1& 3& 2\\ 2& 2& 1& 3& 1& 2\\ 1& 0& 3& 1& 3& 1\\ 1& 2& 2& 2& 1& 4\end{array}\right)& \text{et}& P^3=\left(\begin{array}{cccccc}2& 2& 6& 3& 4& 6\\ 2& 0& 7& 2& 6& 3\\ 6& 7& 4& 9& 3& 9\\ 3& 2& 9& 4& 7& 7\\ 4& 6& 3& 7& 2& 8\\ 6& 3& 9& 7& 8& 6\end{array}\right)\end{array}$$

      Entre les sommets A et B :

      • il n'existe pas de de chaîne de longueur 1 ;
      • il y a une chaîne de longueur 2 ;
      • il y a deux chaînes de longueur 3.

      Il y trois possibilités pour aller d'Atlanta à Boston en utilisant au maximum trois liaisons aériennes : Atlanta - Chicago - Boston, Atlanta - Washington - Chicago - Boston et Atlanta - Washington - New York - Boston.

      ---

---

Rechercher des exercices regoupés par thème

exercices compatibles programme 2012 : ------- Liste des thèmes disponibles -------SuitesFonctions : Lectures graphiquesFonction logarithmeFonction logarithme avec intégraleFonction exponentielleFonction exponentielle avec intégraleCalcul intégralFonctions : Applications économiquesExponentielle : Applications économiquesQuestions ouvertesProbabilitésVariables aléatoires discrètesLoi binomialeLois de probabilité à densitéQCM AnalyseQ.C.M. ProbabilitésQ.C.M. DiversVrai - FauxGraphesGraphes probabilistesGraphes probabilistes et graphesVrai-Faux (spécialité)

indifférent : ------- Liste des thèmes disponibles -------SuitesFonctions : Lectures graphiquesFonctions : Lectures de tableauxFonction logarithmeFonction logarithme avec intégraleFonction exponentielleFonction exponentielle avec intégraleCalcul intégralFonctions : Applications économiquesExponentielle : Applications économiquesAjustement affine d'un nuage de pointsAjustement non affine d'un nuage de pointsAjustement exponentiel d'un nuage de pointsQuestions ouvertesProbabilitésAdéquation à une loi équirépartieVariables aléatoires discrètesLoi binomialeLois de probabilité à densitéQCM AnalyseQ.C.M. ProbabilitésQ.C.M. DiversVrai - FauxVrai - Faux (Probabilités)Réstitution organisée de connaissancesGéométrie dans l'espaceFonctions de deux variablesGraphesGraphes probabilistesGraphes probabilistes et graphesQ.C.M. SpécialitéVrai-Faux (spécialité)

---

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