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.
Marche aléatoire et état stable
Un randonneur passe chaque nuit dans l'un des trois refuges
- s'il est en
, il y reste avec la probabilité , sinon il va en ; - s'il est en
, il va en avec la probabilité , reste en avec la probabilité , sinon il va en ; - s'il est en
, il y reste avec la probabilité , sinon il va en .
On note
- Représenter la situation par un graphe probabiliste, puis écrire la matrice de transition
(états rangés dans l'ordre , , ). - Donner
, puis calculer et . - Quelle est la probabilité que le randonneur dorme en
la nuit ? Quel coefficient de cette probabilité représente-t-elle ? - Montrer que, pour tout entier
, . - Déterminer la distribution invariante
de cette chaîne de Markov. - On admet que
converge vers . Interpréter ce résultat.
Voir la correction détaillée
1Graphe probabiliste et matrice de transition
Un sommet par état ; un arc
Depuis
Contrôle : la somme de chaque ligne vaut
2 , et
Le randonneur est en
Contrôle :
Écrire
3Probabilité d'être en la nuit
Le seul chemin de longueur
4 pour
Écrire le deuxième coefficient de
Avec
Pour tout entier
5Distribution invariante
Écrire le système
- Deuxième équation :
, donc . - Première équation :
, donc . - Troisième équation :
, donc .
La distribution invariante est
6Interprétation
Lorsque
À long terme, le randonneur dort en
Les réponses
; graphe : boucles ( ), ( ), ( ) ; arcs ( ), ( ), ( ), ( ). , , . . . .- À long terme :
des nuits en , en , en .
Graphe orienté et nombre de chemins
On considère le graphe orienté ci-dessous, de sommets
- Écrire la matrice d’adjacence
de ce graphe (sommets rangés dans l’ordre , , , ). - Calculer
et interpréter ses coefficients. - Calculer
et interpréter le coefficient situé ligne , colonne . - Déterminer le nombre de chemins de longueur
de vers , puis les citer. - Un graphe orienté est dit fortement connexe si, pour tous sommets distincts
et , il existe un chemin de vers . Ce graphe est-il fortement connexe ?
Voir la correction détaillée
1Matrice d’adjacence
- Depuis
: et , donc ligne : . - Depuis
: et , donc ligne : . - Depuis
: et , donc ligne : . - Depuis
: , donc ligne : .
2Calcul et interprétation de
Dans
- Ligne
(arcs vers et ) : . - Ligne
(arcs vers et ) : . - Ligne
(arcs vers et ) : . - Ligne
(arc vers ) : .
: un seul chemin, ; : et ; : ; : aucun chemin de longueur ne part de pour revenir en .
3Calcul de
- Ligne
(vers , ) : . - Ligne
(vers , ) : . - Ligne
(vers , ) : . - Ligne
(vers ) : .
Il y a trois chemins de longueur
4Chemins de longueur 2 de vers
Le nombre cherché est
Un chemin de longueur
Il y a
5Le graphe est-il fortement connexe ?
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.
Les arcs
Pour aller d’un sommet
Tous les coefficients de
Le graphe est fortement connexe.
Les réponses
: est le nombre de chemins de longueur de vers . ; : trois chemins de longueur de à . chemins : et .- Oui : le circuit
passe par tous les sommets.
Puissances d'une matrice et suite de matrices
On considère la matrice
- Calculer
, et . - Conjecturer une formule pour
, . - Démontrer par récurrence la formule conjecturée.
- Calculer
, , et . - Exprimer
en fonction de .
Voir la correction détaillée
1Calcul de , ,
2Conjecture
On lit
| Coefficient | ||||
Conjecture : pour tout entier
3Démonstration par récurrence
Pour
Pour
Soit
C’est la formule au rang
Par récurrence, pour tout entier
4Calcul de à
5Expression de
Comme
car
Pour
Pour tout entier
Les réponses
, ,- Conjecture :
- Initialisation pour
, hérédité par le calcul de . , , ,
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’abonnementCours 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