Algorithme de Dijkstra, Graphe probabiliste,

Baccalauréat septembre 2013 MATHÉMATIQUES Série ES-L

sujet : Polynésie

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

Les parties A et B sont indépendantes

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.

Graphe pondéré : L'illustration svg n'est pas visible par votre navigateur.
    1. Le graphe est-il connexe ? Justifier la réponse.

      La chaîne B1 - B2 - B6 - B7 - B4 - B5 - B3 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.


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

      B1 est le seul sommet de degré pair, par conséquent, il n'existe pas de cycle eulérien.

      Il n'existe pas de parcours qui permet de revenir à une balise de départ en passant une et une seule fois par tous les chemins.


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

      Il y a 6 sommets de degré impair, par conséquent, il n'existe pas de chaîne eulérienne.

      Il n'existe pas de parcours qui permet de relier deux balises différentes en passant une et une seule fois par tous les chemins.


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

    À l'aide de l'algorithme de Dijkstra, on détermine l'itinéraire le plus court en temps entre les balises B1 et B7 :

    Algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.

    B1B2B3B4B5B6B7Sommet sélectionné
     0 

    B1 (0)

    21 (B1)13 (B1)

    B3 (13)

    21 (B1)21 (B3)18 (B3)

    B5 (18)

    21 (B1)20 (B5)33 (B5)

    B4 (20)

    21 (B1)24 (B4)33 (B5)

    B2 (21)

    24(B4)33 (B5)

    B6 (24)

    29 (B6)

    B7 (29)


    Le sommet B7 étant marqué, pour lire la chaîne de poids minimal, on part de B7 et on "remonte" la chaîne en suivant les prédécesseurs. B7 ← B6 ← B4 ← B5 ← B3 ← B1.

    La durée minimale du parcours est de 29 minutes en empruntant le chemin B1 - B3 - B5 - B4 - B6 - B7.


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 Pn=(xnyn)xn 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.

    On considère que :

    • 70% des licenciés ayant adhéré en 2011 ont conservé cette assurance d'où pAn(An+1)=0,7 et pAn(Bn+1)=0,3
    • 60% de ceux n'ayant pas adhéré en 2011 ont adhéré en 2012 d'où pBn(An+1)=0,6 et pBn(Bn+1)=0,4

    D'où le graphe probabiliste correspondant à cette situation :

    Graphe probabiliste : L'illustration svg n'est pas visible par votre navigateur.
  2. Écrire la matrice de transition M de ce graphe en prenant les sommets A et B dans cet ordre.

    La matrice de transition M de ce graphe telle que (xn+1yn+1)=(xnyn)×M est : M=(0,70,30,60,4).


  3. En remarquant que P0=(0,80,2), déterminer P1. Interpréter ce résultat.

    La première année, 80% des licenciés ont adhéré à l'assurance donc l'état intial est P0=(0,80,2). L'état P1 est : P1=P0×MSoitP1=(0,80,2)×(0,70,30,60,4)P1=(0,680,32)

    P1=(0,680,32) donc en 2012, 68% des licenciés ont adhéré à l'assurance.


  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 ?

    Les termes de la matrice de tansition M d'ordre 2 ne sont pas de nuls, alors l'état Pn converge vers un état stable P=(xy) vérifiant : (xy)=(xy)×(0,70,30,60,4)(xy)=(0,7x+0,6y0,3x+0,4y)

    D'où x et y vérifient la relation x=0,7x+0,6y. Comme d'autre part, x+y=1 on en déduit que x et y sont solutions du système : {x=0,7x+0,6yx+y=1{0,3x-0,6y=0x+y=1{0,9x=0,6x+y=1{x=23y=13

    L'état stable du système est P=(2313). Sur le long terme, d'une année sur l'autre, le nombre d'assurés restera supérieur à 66%. Le club sportif maintiendra son offre d'assurance spécifique.



Rechercher des exercices regoupés par thème


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