Graphes, matrices et chaînes de Markov
🟡 Moyen📝 Les énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.
- 1
On considère le graphe non orienté à 4 sommets A, B, C, D dont les arêtes sont A−B, B−C, C−D et B−D.
a) Écrire la matrice d'adjacence M (ordre A, B, C, D).
b) Calculer M².
c) Combien y a-t-il de chaînes de longueur 2 partant de B et revenant à B ? Combien de chaînes de longueur 2 relient A à D ?✅ Voir le corrigéoffert
a) A est relié à B ; B à A, C, D ; C à B, D ; D à B, C.
M =
( 0 1 0 0 )
( 1 0 1 1 )
( 0 1 0 1 )
( 0 1 1 0 )
b) On calcule M² = M × M ligne par ligne.
Ligne A = ( 0 1 0 0 ) : elle sélectionne la ligne B de M, donc ligne A de M² = ( 1 0 1 1 ).
Ligne B = ( 1 0 1 1 ) : somme des lignes A, C, D de M = ( 0 1 0 0 ) + ( 0 1 0 1 ) + ( 0 1 1 0 ) = ( 0 3 1 1 ).
Ligne C = ( 0 1 0 1 ) : somme des lignes B et D = ( 1 0 1 1 ) + ( 0 1 1 0 ) = ( 1 1 2 1 ).
Ligne D = ( 0 1 1 0 ) : somme des lignes B et C = ( 1 0 1 1 ) + ( 0 1 0 1 ) = ( 1 1 1 2 ).
M² =
( 1 0 1 1 )
( 0 3 1 1 )
( 1 1 2 1 )
( 1 1 1 2 )
c) Chaînes de longueur 2 de B à B : = 3 (ce sont B−A−B, B−C−B, B−D−B).
Chaînes de longueur 2 de A à D : = 1 (c'est A−B−D). - 2
Une chaîne de Markov à deux états A et B a pour matrice de transition
M =
( 0,8 0,2 )
( 0,3 0,7 )
Déterminer l'état stable P = ( x y ), c'est-à-dire le vecteur ligne tel que x + y = 1 et P = P × M.✅ Voir le corrigéoffert
L'état stable vérifie P = P × M avec x + y = 1.
P × M = ( 0,8x + 0,3y ; 0,2x + 0,7y ).
L'égalité P = P × M donne, sur la 1re coordonnée : x = 0,8x + 0,3y.
On remplace y par 1 − x : x = 0,8x + 0,3(1 − x) = 0,8x + 0,3 − 0,3x = 0,5x + 0,3.
Donc x − 0,5x = 0,3, soit 0,5x = 0,3, d'où x = 0,6.
Alors y = 1 − 0,6 = 0,4.
État stable : P = ( 0,6 0,4 ).
Vérification : P × M = ( 0,6×0,8 + 0,4×0,3 ; 0,6×0,2 + 0,4×0,7 ) = ( 0,48+0,12 ; 0,12+0,28 ) = ( 0,6 0,4 ) = P. C'est correct. - 3
Deux marques A et B se partagent un marché. Chaque année, 10 % des clients de A passent à B, et 20 % des clients de B passent à A. Au départ, 40 % des clients sont chez A.
a) Écrire la matrice de transition M et l'état initial P₀.
b) Déterminer la répartition après 2 ans.
c) Déterminer l'état stable à long terme.🔒 Corrigé réservé aux abonnésS'abonner → - 4
Une chaîne de Markov à trois états 1, 2, 3 a pour matrice de transition
M =
( 0,5 0,3 0,2 )
( 0,1 0,6 0,3 )
( 0,4 0,4 0,2 )
Sachant qu'on part de l'état 1, c'est-à-dire P₀ = ( 1 0 0 ), calculer P₁ puis P₂.🔒 Corrigé réservé aux abonnésS'abonner → - 5
On considère le graphe complet à 4 sommets 1, 2, 3, 4 (chaque sommet est relié à tous les autres), de matrice d'adjacence M dont tous les coefficients hors diagonale valent 1 et la diagonale est nulle.
a) Combien y a-t-il de chaînes de longueur 2 reliant deux sommets distincts, par exemple 1 et 2 ?
b) Combien y a-t-il de chaînes de longueur 2 reliant un sommet à lui-même, par exemple 1 à 1 ?🔒 Corrigé réservé aux abonnésS'abonner → - 6
Une chaîne de Markov à deux états A et B a pour matrice de transition
M =
( 0,7 0,3 )
( 0,4 0,6 )
On note aₙ la probabilité d'être dans l'état A à l'étape n.
a) Justifier que aₙ₊₁ = 0,4 + 0,3 aₙ.
b) En déduire la limite de la suite (aₙ).🔒 Corrigé réservé aux abonnésS'abonner → - 7
a) Un graphe est dit k-régulier lorsque tous ses sommets ont le même degré k. Combien d'arêtes possède un graphe 3-régulier à 8 sommets ?
b) Existe-t-il un graphe 3-régulier à 7 sommets ? Justifier.🔒 Corrigé réservé aux abonnésS'abonner → - 8
On considère un graphe à 4 sommets A, B, C, D dont les seules arêtes sont A−B et C−D.
a) Écrire la matrice d'adjacence M.
b) Le graphe est-il connexe ? Justifier en s'appuyant sur les chaînes.🔒 Corrigé réservé aux abonnésS'abonner → - 9
Un mobile se déplace entre trois positions 1, 2, 3. À chaque étape : depuis 1 il va en 2 (proba 0,6) ou reste en 1 (proba 0,4) ; depuis 2 il va en 1 (proba 0,3), reste en 2 (proba 0,3) ou va en 3 (proba 0,4) ; depuis 3 il va en 2 (proba 0,5) ou reste en 3 (proba 0,5).
a) Écrire la matrice de transition M.
b) Vérifier que M est une matrice stochastique.🔒 Corrigé réservé aux abonnésS'abonner → - 10
Un jeton se déplace au hasard sur les 3 sommets d'un triangle 1, 2, 3. À chaque étape, il passe sur l'un des deux autres sommets, chacun avec la probabilité 0,5.
a) Écrire la matrice de transition M.
b) Déterminer l'état stable P = ( x y z ).🔒 Corrigé réservé aux abonnésS'abonner →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.