sujet : amérique du nord

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

partie a : Étude d'un site

1. Le technicien souhaite tester les liens de pages. En partant de la page A, est-il possible de trouver un parcours passant une seule fois par tous les liens de pages ? Justifier la réponse.

   Trouver un parcours passant une seule fois par tous les liens de pages c'est chercher si le graphe admet une chaîne eulérienne.

   Or les sommets A, B, D et G sont de degré 3. Le nombre de sommets de degré impair étant supérieur à 2, il n'existe pas de chaîne eulérienne.

   Le graphe n'admet pas de chaîne eulérienne, donc il n'existe pas de parcours passant une seule fois par tous les liens de pages.

   ---

2. Pour marquer les changements de page, l'administrateur du site souhaite que deux pages reliées aient des couleurs différentes.
   On note N le nombre minimum de couleurs nécessaires.

   1. Donner  un sous-graphe complet d'ordre maximal.

      Les sous-graphes complets d'ordre maximal sont d'ordre 3. Par exemple le sous-graphe (A, B, C).

      ---

   2. En utilisant la question 2. a. et à l'aide d'un algorithme, montrer, que $N=3$.

      Le plus haut degré des sommets est 4 (sommets C, E ou F) par conséquent , le nombre chromatique $N⩽5$. D'autre part, un sous-graphe complet d'ordre maximal est d'ordre 3. Donc $3⩽N⩽5$.

      L'algorithme de Welsh & Powell donne une coloration du graphe à l'aide de trois couleurs :

      ---

      $3⩽N⩽5$ et une coloration avec trois couleurs est possible donc $N=3$.

      ---

partie b : Étude de propagation d'un virus d'un site à l'autre

1. Justifier la valeur 0 indiquée sur le graphe probabiliste précédent, puis recopier et compléter ce graphe sur votre copie.

   Si le site n'est pas infecté par le virus, la probabilité de propager le virus au site suivant est nulle. Soit $p_S\left(V\right)=0$ et $p_S\left(S\right)=1$.

   Si le site est infecté par le virus comme les antivirus ne sont efficaces qu'à 80 %, la probabilité de propager le virus au site suivant est 0,2. $p_V\left(V\right)=\mathrm{0,2}$ et $p_V\left(S\right)=\mathrm{0,8}$.

   D'où le graphe probabiliste traduisant les risques de propagation du virus d'un site au suivant :

2. Préciser la matrice de transition M de ce graphe (première ligne pour V, deuxième ligne pour S)

   La matrice de transition M de ce graphe (première ligne pour V, deuxième ligne pour S) est : $M=\left(\begin{array}{cc}\mathrm{0,2}& \mathrm{0,8}\\ 0& 1\end{array}\right)$.

   ---

3. Pour tout entier naturel non nul n, on note :
   $P_n$ la probabilité que le n-ième site soit infecté, $Q_n$ la probabilité que le n-ième site soit sain et $X_n=\left(\begin{array}{cc}{P}_n& Q_n\end{array}\right)$.
   On a donc $X_1=\left(\begin{array}{cc}1& 0\end{array}\right)$ (traduisant que le site № 1 est infecté) et $X_{n+1}=X_{n}M$.

   1. En utilisant la relation $X_{n+1}=X_{n}M$, montrer que $P_{n+1}=\mathrm{0,2}{P}_n$.

      $$\begin{array}{ccc}{X}_{n+1}=X_{n}M& \iff & \left(\begin{array}{cc}{P}_{n+1}& Q_{n+1}\end{array}\right)=\left(\begin{array}{cc}{P}_n& Q_n\end{array}\right)\left(\begin{array}{cc}\mathrm{0,2}& \mathrm{0,8}\\ 0& 1\end{array}\right)\hfill \\ & \iff & \left(\begin{array}{cc}{P}_{n+1}& Q_{n+1}\end{array}\right)=\left(\begin{array}{cc}\mathrm{0,2}{P}_n& \mathrm{0,8}{P}_n+Q_n\end{array}\right)\hfill \end{array}$$

      Ainsi, pour tout entier naturel non nul n, $P_{n+1}=\mathrm{0,2}{P}_n$.

      ---

   2. En déduire $P_n$ en fonction de n.

      Pour tout entier naturel non nul n, $P_{n+1}=\mathrm{0,2}{P}_n$ donc $\left(P_n\right)$ est une suite gémétrique de raison 0,2. Le premier terme de cette suite est $P_1=1$

      Donc pour tout entier naturel non nul n, $P_n={\mathrm{0,2}}^{n-1}$.

      ---

   3. Déterminer la limite de la suite $\left(P_n\right)$ lorsque n tend vers plus l'infini.

      $0<\mathrm{0,2}<1$ donc $\underset{x\to +\infty }{\lim }{\mathrm{0,2}}^{n-1}=0$.

      La suite $\left(P_n\right)$ converge vers 0. Au bout d'un nombre de sites suffisamment grand, la probabilité de propager le virus est quasiment nulle.

      ---

---

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.