On considère le graphe non orienté G de sommets A,B,C,D et d'arêtes A–B,A–C,B–C et C–D.
Écris la matrice d'adjacence M du graphe, dans l'ordre A,B,C,D. Pourquoi est-elle symétrique ?
Voir le corrigé
M=0110101011010010. Le coefficient (i;j) vaut 1 s'il y a une arête entre les sommets i et j. Le graphe n'est pas orienté : i–j est aussi j–i, d'où la symétrie.
c.π=(x1−x) avec 0,7x+0,4(1−x)=x : 0,4=0,7x,π=(7473).
Chaîne de Markov : si πn est la loi (ligne) à l'étape n et P la matrice de transition, alors πn+1=πnP et πn=π0Pn. Un état stable vérifie πP=π, avec des coefficients de somme 1.
Un client achète chaque semaine l'une des marques 1,2 ou 3 selon la matrice de transition
P=0,70,30,20,20,50,30,10,20,5. Cette semaine, il achète la marque 1.
Calcule la loi des marques achetées dans une semaine, puis dans deux semaines.
Voir le corrigé
π0=(100),π1=(0,70,20,1) (première ligne de P),π2=π1P=(0,49+0,06+0,020,14+0,1+0,030,07+0,04+0,05)=(0,570,270,16).
Un pion se déplace sur les sommets A,B,C d'un triangle : à chaque étape, il va sur l'un des deux autres sommets, avec la même probabilité. Il part de A ; an est la probabilité qu'il soit en A à l'étape n.
a. Donne la matrice de transition et l'état stable.
b. Montre que an+1=21−an, puis que an=31+32(−21)n.
Voir le corrigé
a.P=021212102121210. Par symétrie, l'état stable est (313131).
b. Pour être en A à l'étape n+1, il faut ne pas y être à l'étape n (probabilité 1−an) puis choisir A (21).an−31 est géométrique de raison −21 et vaut 32 au départ : on obtient la formule. an→31.
Cinq personnes A,B,C,D,E sont reliées par les amitiés A–B,A–C,B–C,B–D,C–E et D–E.
1. Représente le graphe et donne le degré de chaque sommet. Qui a le plus d'amis ?
2. Écris la matrice d'adjacence M (ordre alphabétique).
3. On admet que M2=2111113102113201022012002. Combien d'amis communs ont B et E ? Qui sont-ils ?
4. Deux personnes non amies sont « amies d'amis » si elles ont au moins un ami commun. Quelles paires ne sont ni amies, ni amies d'amis ?
Voir le corrigé
1.A : 2,B : 3,C : 3,D : 2,E : 2. B et C ont le plus d'amis.
2.M=0110010110110010100100110.
3. Coefficient (B;E) : 2 amis communs, C et D.
4. Les paires non amies sont (A;D),(A;E),(B;E) et (C;D). Leurs coefficients dans M2 valent 1,1,2 et 2, tous non nuls :
aucune paire n'est ni amie, ni amie d'amis.
Exercice 14type contrôleDeux plateformes de streaming
Chaque mois, 20% des abonnés de la plateforme A passent chez B et 10% des abonnés de B passent chez A. Au départ, les deux plateformes ont autant d'abonnés.
1. Donne la matrice de transition P (état 1 : A, état 2 : B) et π0.
2. Calcule π1.
3. On note πn=(an1−an). Montre que an+1=0,7an+0,1.
4. Déduis-en an en fonction de n, sa limite, et l'état stable.
5. À partir de quel mois la part de A passe-t-elle sous 34% ?
Voir le corrigé
1.P=(0,80,10,20,9), π0=(0,50,5).
2.π1=(0,4+0,050,1+0,45)=(0,450,55).
3.an+1=0,8an+0,1(1−an)=0,7an+0,1.
4. Point fixe 31 : an=31+61×0,7n, an→31, état stable (3132).
5.61×0,7n<0,34−31=1501⟺0,7n<0,04⟺n>ln0,7ln0,04≈9,02 : au 10e mois.
Dans une ville, chaque habitant lit chaque jour le journal X ou le journal Y. Un lecteur de X reste fidèle le lendemain avec probabilité 0,9 ; un lecteur de Y passe à X avec probabilité 0,3.
Le premier jour, 40% des habitants lisent X.
1. Représente la situation par un graphe probabiliste et donne la matrice de transition P.
2. Calcule la répartition le deuxième jour.
3. Détermine l'état stable et interprète-le.
4. On admet que xn=0,75−0,35×0,6n, où xn est la part de X le jour n (n⩾0). Vérifie pour n=0 et n=1, puis détermine à partir de quel jour X dépasse 70%.
Voir le corrigé
1. Deux sommets X et Y, arcs pondérés 0,9 (X→X),0,1 (X→Y),0,3 (Y→X),0,7 (Y→Y).P=(0,90,30,10,7).
2.(0,40,6)P=(0,36+0,180,04+0,42)=(0,540,46).
3.0,9x+0,3(1−x)=x⟺0,3=0,4x : (0,750,25). À long terme, 75% des habitants lisent X.
4.x0=0,4 et x1=0,75−0,21=0,54.0,35×0,6n<0,05⟺0,6n<71⟺n>ln(1/0,6)ln7≈3,8 : à partir de n=4, soit le cinquième jour.
Qu'est-ce que la matrice d'adjacence d'un graphe ?
C'est la matrice dont le coefficient ligne i, colonne j vaut 1 s'il y a une arête (ou un arc) de i vers j, et 0 sinon. Pour un graphe non orienté, elle est symétrique.
Comment compter les chemins de longueur n ?
Le coefficient ligne i, colonne j de la puissance Mⁿ de la matrice d'adjacence est le nombre de chemins de longueur n allant de i à j.
Qu'est-ce qu'une chaîne de Markov ?
C'est une suite d'états aléatoires où l'état suivant ne dépend que de l'état présent. Elle est décrite par une matrice de transition P, dont chaque ligne a pour somme 1, et la loi évolue selon π(n+1) = π(n) × P.
Comment trouver l'état stable d'une chaîne de Markov ?
On résout πP = π avec la condition que la somme des coefficients de π vaut 1. Pour deux états, on obtient une équation du premier degré.
Les exercices sont-ils gratuits ?
Oui. Les 16 exercices et leurs corrigés sont gratuits, en ligne et en PDF à imprimer, sans inscription.