GRAPHES

Graphes

• Exercice : Graphes et matrices

  Partie A

  Un club sportif organise une course d’orientation. Sept postes de contrôles (appelés balises) sont prévus.

  Les sept balises notées B1 ; B2 ; . . . ; B7 sont représentées sur le graphe ci-dessous.

  Les arêtes du graphe représentent les chemins possibles entre les balises et sur chaque arête est indiqué le temps de parcours estimé en minutes.

  

  1) a) Le graphe est-il connexe ? Justifier la réponse.

       b) Existe-t-il un parcours qui permet de revenir à une balise de départ en passant une et une seule fois par tous les chemins ? Justifier la réponse.

       c) Existe-t-il un parcours qui permet de relier deux balises différentes en passant une et une seule fois par tous les chemins ?

  2) Les organisateurs décident de situer le départ à la balise B1 et l’arrivée à la balise B7.

  Chaque participant doit rallier la balise B7 en un minimum de temps. Ils ne sont pas tenus à emprunter tous les chemins.

  Quelle est la durée minimale du parcours possible et quel est ce parcours ? Justifier votre réponse à l’aide d’un algorithme.

   

  Partie B

  Depuis l’année 2011, ce club sportif propose à ses licenciés une assurance spécifique. La première année, 80% des licenciés y ont adhéré.

  En 2012, 70% des licenciés ayant adhéré en 2011 ont conservé cette assurance et 60% de ceux n’ayant pas adhéré en 2011 ont adhéré en 2012.

  En supposant que cette évolution se maintienne, le club sportif souhaite savoir quel pourcentage de licenciés adhèrera à cette assurance à plus long terme.

  On note :

  $A$ « le licencié est assuré »

  $B$ « le licencié n’est pas assuré »

  Pour tout entier $n$ non nul, l’état probabiliste du nombre d’assurés l’année $2011+n$ est défini par la matrice ligne :

  $P_n \begin{pmatrix} x_n&y_n \end{pmatrix}$ où $x_n$  désigne la probabilité pour un licencié d’être assuré l’année  $2011+n$.

   

  1) Représenter cette situation par un graphe probabiliste de sommets $A$ et $B$.

  2) Écrire la matrice de transition $M$ de ce graphe en prenant les sommets $A$ et$B$ dans cet ordre.

  3) En remarquant que $P_0 = \begin{pmatrix} 0,8&0,2 \end{pmatrix}$, déterminer $P_1$. Interpréter ce résultat.

  4) Le club sportif maintiendra son offre d’assurance spécifique si le nombre d’assurés reste supérieur à $55$%.

  L’évolution prévue lui permet-elle d’envisager le maintien de son offre à long terme ?

  Afficher la correction

  ---