Aller au contenu
OptiTAB

Maths Terminale · Chapitre 24 · Maths Expertes

Graphes et matrices : exercices corrigés

3 exercices corrigés sur « Graphes et matrices » (Terminale), du plus simple au plus complet. Cherche d’abord sur ton brouillon, puis ouvre la correction détaillée.

Exercice 1 Intermédiaire Entraînement

Marche aléatoire et état stable

Un randonneur passe chaque nuit dans l'un des trois refuges A, B, C d'un massif ; les refuges A et C ne sont reliés que par l'intermédiaire de B. Chaque matin, il choisit sa prochaine étape ainsi :

  • s'il est en A, il y reste avec la probabilité 0,7, sinon il va en B ;
  • s'il est en B, il va en A avec la probabilité 0,2, reste en B avec la probabilité 0,3, sinon il va en C ;
  • s'il est en C, il y reste avec la probabilité 0,7, sinon il va en B.

On note Xn le refuge de la nuit n et πn=(P(Xn=A)P(Xn=B)P(Xn=C)). La nuit 0, le randonneur dort en A.

  1. Représenter la situation par un graphe probabiliste, puis écrire la matrice de transition P (états rangés dans l'ordre A, B, C).
  2. Donner π0, puis calculer π1 et π2.
  3. Quelle est la probabilité que le randonneur dorme en C la nuit 2 ? Quel coefficient de P2 cette probabilité représente-t-elle ?
  4. Montrer que, pour tout entier n≥1, P(Xn=B)=0,3.
  5. Déterminer la distribution invariante π=(abc) de cette chaîne de Markov.
  6. On admet que πn converge vers π. Interpréter ce résultat.
Voir la correction détaillée

1Graphe probabiliste et matrice de transition

Méthode

Un sommet par état ; un arc i→j portant la probabilité pij de passer de i à j (une boucle pour rester sur place). La ligne i de P contient les probabilités des arcs qui partent de i.

Étape 1Le graphe

Depuis A : boucle 0,7 et arc vers B de poids 1−0,7=0,3. Depuis B : arcs vers A (0,2), vers C (1−0,2−0,3=0,5) et boucle 0,3. Depuis C : boucle 0,7 et arc vers B de poids 0,3.

Graphe probabiliste des refuges A, B, C : boucles 0,7 en A, 0,3 en B, 0,7 en C ; arcs A vers B 0,3, B vers A 0,2, B vers C 0,5, C vers B 0,3
Étape 2La matrice de transition
P=(0,70,300,20,30,500,30,7)

Contrôle : la somme de chaque ligne vaut 1 (0,7+0,3 ; 0,2+0,3+0,5 ; 0,3+0,7).

Résultat
P=(0,70,300,20,30,500,30,7)

2π0, π1 et π2

Méthode

πn+1=πnP : la distribution est une matrice ligne, placée à gauche de P.

Étape 1Distribution initiale et π1

Le randonneur est en A la nuit 0 : π0=(100). Alors π1=π0P est la première ligne de P :

π1=(0,70,30)
Étape 2Calcul de π2=π1P, coefficient par coefficient
0,7×0,7+0,3×0,2+0×0=0,550,7×0,3+0,3×0,3+0×0,3=0,30,7×0+0,3×0,5+0×0,7=0,15

Contrôle : 0,55+0,3+0,15=1.

Résultat

π0=(100), π1=(0,70,30) et π2=(0,550,30,15).

AttentionErreur fréquente

Écrire Pπn au lieu de πnP : avec des lignes de P correspondant aux états de départ, la distribution se multiplie à gauche.

3Probabilité d'être en C la nuit 2

Étape 1Lecture de π2

P(X2=C) est le troisième coefficient de π2 : 0,15.

Étape 2Lien avec P2

π2=π0P2 et π0=(100) : π2 est la première ligne de P2. Donc 0,15=(P2)AC, la probabilité de passer de A à C en deux transitions.

Vérification sur le graphe

Le seul chemin de longueur 2 de A à C est A→B→C (il n'y a pas d'arc A→C) : sa probabilité est 0,3×0,5=0,15.

Résultat

P(X2=C)=0,15 : c'est le coefficient (P2)AC, ligne A et colonne C de P2.

4P(Xn=B)=0,3 pour n≥1

Méthode

Écrire le deuxième coefficient de πn+1=πnP et remarquer que la colonne B de P est constante.

Étape 1Deuxième coefficient de πn+1

Avec πn=(anbncn) :

bn+1=0,3an+0,3bn+0,3cn=0,3(an+bn+cn)
Étape 2Conclure

an+bn+cn=1 (les trois états forment une partition), donc bn+1=0,3 pour tout entier n≥0.

Résultat

Pour tout entier n≥1, P(Xn=B)=0,3 : quel que soit le refuge de la veille, il va en B avec la probabilité 0,3.

5Distribution invariante

Méthode

Écrire le système πP=π, puis ajouter la condition a+b+c=1.

Étape 1Le système πP=π
{0,7a+0,2b=a0,3a+0,3b+0,3c=b0,5b+0,7c=c
Étape 2Résolution avec a+b+c=1
  • Deuxième équation : 0,3(a+b+c)=b, donc b=0,3.
  • Première équation : 0,2b=0,3a, donc a=0,2×0,30,3=0,2.
  • Troisième équation : 0,5b=0,3c, donc c=0,5×0,30,3=0,5.
Vérification

0,2+0,3+0,5=1. Première équation : 0,7×0,2+0,2×0,3=0,2, c'est bien a.

Résultat

La distribution invariante est π=(0,20,30,5).

6Interprétation

Étape 1État stable

Lorsque n devient grand, P(Xn=A), P(Xn=B) et P(Xn=C) se rapprochent de 0,2, 0,3 et 0,5 : c'est l'état stable de la marche.

Probabilités d'être en A, B et C la nuit n pour un départ en A : elles se rapprochent de 0,2, 0,3 et 0,5
Résultat

À long terme, le randonneur dort en C une nuit sur deux en moyenne, en B 30% des nuits et en A 20% des nuits, quel que soit son refuge de départ.

Les réponses

  1. P=(0,70,300,20,30,500,30,7) ; graphe : boucles 0,7 (A), 0,3 (B), 0,7 (C) ; arcs A→B (0,3), B→A (0,2), B→C (0,5), C→B (0,3).
  2. π0=(100), π1=(0,70,30), π2=(0,550,30,15).
  3. P(X2=C)=0,15=(P2)AC.
  4. bn+1=0,3(an+bn+cn)=0,3.
  5. π=(0,20,30,5).
  6. À long terme : 20% des nuits en A, 30% en B, 50% en C.
Exercice 2 Intermédiaire Type examen

Graphe orienté et nombre de chemins

On considère le graphe orienté ci-dessous, de sommets A, B, C, D, dont les arcs sont A→B, A→C, B→C, B→D, C→A, C→D et D→A.

Graphe orienté à quatre sommets A, B, C, D avec les arcs A-B, A-C, B-C, B-D, C-A, C-D et D-A
  1. Écrire la matrice d’adjacence M de ce graphe (sommets rangés dans l’ordre A, B, C, D).
  2. Calculer M2 et interpréter ses coefficients.
  3. Calculer M3 et interpréter le coefficient situé ligne A, colonne A.
  4. Déterminer le nombre de chemins de longueur 2 de A vers D, puis les citer.
  5. Un graphe orienté est dit fortement connexe si, pour tous sommets distincts X et Y, il existe un chemin de X vers Y. Ce graphe est-il fortement connexe ?
Voir la correction détaillée

1Matrice d’adjacence

Méthode

mij=1 s’il existe un arc du sommet i vers le sommet j, 0 sinon ; la ligne correspond au départ, la colonne à l’arrivée.

Étape 1Lire les arcs sommet par sommet
  • Depuis A : A→B et A→C, donc ligne A : (0110).
  • Depuis B : B→C et B→D, donc ligne B : (0011).
  • Depuis C : C→A et C→D, donc ligne C : (1001).
  • Depuis D : D→A, donc ligne D : (1000).
Résultat
M=(0110001110011000)

2Calcul et interprétation de M2

Méthode

Dans M2=M×M, la ligne d’un sommet X est la somme des lignes de M des sommets atteints depuis X par un arc (c’est le calcul « ligne par colonne » regroupé).

Étape 1Vérifier la méthode sur un coefficient

(M2)AD=0×0+1×1+1×1+0×0=2 (ligne A de M par colonne D de M).

Étape 2Calculer les quatre lignes
  • Ligne A (arcs vers B et C) : (0011)+(1001)=(1012).
  • Ligne B (arcs vers C et D) : (1001)+(1000)=(2001).
  • Ligne C (arcs vers A et D) : (0110)+(1000)=(1110).
  • Ligne D (arc vers A) : (0110).
Résultat
M2=(1012200111100110)
Interprétation

(M2)XY est le nombre de chemins de longueur 2 de X vers Y. Par exemple :

  • (M2)AA=1 : un seul chemin, A→C→A ;
  • (M2)BA=2 : B→C→A et B→D→A ;
  • (M2)CB=1 : C→A→B ;
  • (M2)BB=0 : aucun chemin de longueur 2 ne part de B pour revenir en B.

3Calcul de M3

Méthode

M3=M×M2 : la ligne d’un sommet X est la somme des lignes de M2 des sommets atteints depuis X par un arc.

Étape 1Calculer les quatre lignes
  • Ligne A (vers B, C) : (2001)+(1110)=(3111).
  • Ligne B (vers C, D) : (1110)+(0110)=(1220).
  • Ligne C (vers A, D) : (1012)+(0110)=(1122).
  • Ligne D (vers A) : (1012).
Résultat
M3=(3111122011221012)
Interprétation de (M3)AA=3

Il y a trois chemins de longueur 3 qui partent de A et y reviennent : A→B→C→A, A→B→D→A et A→C→D→A.

4Chemins de longueur 2 de A vers D

Étape 1Lire le coefficient

Le nombre cherché est (M2)AD, ligne A et colonne D de M2 : il vaut 2.

Étape 2Citer les chemins

Un chemin de longueur 2 de A vers D passe par un sommet intermédiaire X avec A→X et X→D. Depuis A, on peut aller en B ou en C, et les deux arcs B→D et C→D existent.

Les deux chemins de longueur 2 de A vers D, en vert : A-B-D et A-C-D
Résultat

Il y a 2 chemins de longueur 2 de A vers D : A→B→D et A→C→D.

5Le graphe est-il fortement connexe ?

Méthode

Chercher un circuit (chemin fermé) qui passe par tous les sommets : en le suivant, on va de n’importe quel sommet à n’importe quel autre.

Étape 1Trouver un circuit passant par tous les sommets

Les arcs A→B, B→C, C→D et D→A existent : A→B→C→D→A est un circuit qui passe par les quatre sommets.

Étape 2Conclure

Pour aller d’un sommet X à un sommet Y, il suffit de suivre ce circuit depuis X jusqu’à Y. Le graphe est donc fortement connexe.

RemarqueContrôle matriciel

Tous les coefficients de I4+M+M2+M3=(5233333232432123) sont non nuls : chaque sommet en atteint chaque autre par un chemin de longueur au plus 3.

Résultat

Le graphe est fortement connexe.

Les réponses

  1. M=(0110001110011000)
  2. M2=(1012200111100110) : (M2)XY est le nombre de chemins de longueur 2 de X vers Y.
  3. M3=(3111122011221012) ; (M3)AA=3 : trois chemins de longueur 3 de A à A.
  4. 2 chemins : A→B→D et A→C→D.
  5. Oui : le circuit A→B→C→D→A passe par tous les sommets.
Exercice 3 Difficile Problème

Puissances d'une matrice et suite de matrices

On considère la matrice A=(2102) et la suite de matrices colonnes (Mn) définie par M0=(11) et, pour tout entier naturel n, Mn+1=A×Mn.

  1. Calculer A2, A3 et A4.
  2. Conjecturer une formule pour An, n≥1.
  3. Démontrer par récurrence la formule conjecturée.
  4. Calculer M1, M2, M3 et M4.
  5. Exprimer Mn en fonction de n.
Voir la correction détaillée

1Calcul de A2, A3, A4

Étape 1Calculer A2
A2=(2102)(2102)=(2×2+1×02×1+1×20×2+2×00×1+2×2)=(4404)
Étape 2Calculer A3=A2×A
A3=(4404)(2102)=(84+808)=(81208)
Étape 3Calculer A4=A3×A
A4=(81208)(2102)=(168+24016)=(1632016)
Résultat

A2=(4404), A3=(81208) et A4=(1632016).

2Conjecture

Étape 1Coefficients diagonaux

On lit 2n sur la diagonale : 2,4,8,16.

Étape 2Coefficient en haut à droite
n1234
Coefficient141232
n×2n−11×12×23×44×8
Résultat

Conjecture : pour tout entier n≥1, An=(2nn×2n−102n).

3Démonstration par récurrence

Étape 1Énoncer la propriété

Pour n≥1, on note P(n) : « An=(2nn×2n−102n) ».

Étape 2Initialisation

Pour n=1 : (211×20021)=(2102)=A. Donc P(1) est vraie.

Étape 3Hérédité

Soit k≥1 tel que P(k) est vraie. Alors Ak+1=Ak×A=(2kk×2k−102k)(2102), d’où

(Ak+1)11=2k×2+k×2k−1×0=2k+1(Ak+1)12=2k×1+k×2k−1×2=2k+k×2k=(k+1)×2k(Ak+1)21=0×2+2k×0=0(Ak+1)22=0×1+2k×2=2k+1

C’est la formule au rang k+1 : P(k+1) est vraie.

Résultat

Par récurrence, pour tout entier n≥1, An=(2nn×2n−102n).

4Calcul de M1 à M4

Étape 1Appliquer Mn+1=AMn
M1=(2102)(11)=(2+12)=(32)M2=(2102)(32)=(6+24)=(84)M3=(2102)(84)=(16+48)=(208)M4=(2102)(208)=(40+816)=(4816)
Résultat

M1=(32), M2=(84), M3=(208) et M4=(4816).

5Expression de Mn

Méthode

Comme Mn+1=AMn, on a Mn=AnM0 pour tout entier n ; on utilise la formule de An.

Étape 1Calculer le produit
Mn=AnM0=(2nn×2n−102n)(11)=(2n+n×2n−12n)=((n+2)×2n−12n)

car 2n=2×2n−1.

Vérification

Pour n=4 : 6×23=48 et 24=16, on retrouve M4.

Résultat

Pour tout entier n≥1 : Mn=((n+2)×2n−12n).

Les réponses

  1. A2=(4404), A3=(81208), A4=(1632016)
  2. Conjecture : An=(2nn×2n−102n)
  3. Initialisation pour n=1, hérédité par le calcul de Ak×A.
  4. M1=(32), M2=(84), M3=(208), M4=(4816)
  5. Mn=((n+2)×2n−12n)

Besoin de revoir une notion ?

Plateforme OptiTAB

S’entraîner jusqu’à maîtriser le programme de Terminale

Les 12 exercices corrigés de ce chapitre, le suivi de tes progrès et des révisions guidées.

Découvrir l’abonnement

Cours particuliers

Un prof de maths en Terminale, en ligne

Des séances individuelles avec un professeur, à distance, pour comprendre, combler ses lacunes et préparer les contrôles et le bac.

Réserver un cours particulier