↩ Chapitre : Matrices et graphes (Maths expertes)
L’essentiel de la partie Graphes et matrices du programme de Maths expertes (programme de 2019) : vocabulaire des graphes, matrice d’adjacence, chaînes de Markov et distribution invariante.
1. Graphes
- Un graphe est formé de sommets reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). L’ordre est le nombre de sommets ; le degré d’un sommet est le nombre d’arêtes qui en partent.
- Une chaîne (un chemin dans un graphe orienté) est une suite de sommets consécutifs reliés ; sa longueur est son nombre d’arêtes. Un cycle est une chaîne fermée.
- Graphe complet : deux sommets distincts quelconques sont reliés. Graphe connexe : deux sommets quelconques sont reliés par une chaîne.
2. Matrice d’adjacence
À connaître
- La matrice d’adjacence
d’un graphe à
sommets numérotés a pour coefficient
le nombre d’arêtes (ou d’arcs) allant du sommet
au sommet
. Elle est symétrique pour un graphe non orienté. - Le coefficient
de
est le nombre de chaînes (ou chemins) de longueur
allant de
à
.
3. Chaînes de Markov
À connaître
- Une chaîne de Markov sur un ensemble fini d’états est décrite par un graphe orienté pondéré par des probabilités de transition ; la somme des poids des arcs issus d’un sommet vaut
. - La matrice de transition
a pour coefficient
la probabilité de passer de l’état
à l’état
; ses lignes ont une somme égale à
. - Si
est la loi (matrice ligne) à l’étape
:
et
. - Une distribution invariante
vérifie
, avec des coefficients positifs de somme
.
- Exemple à deux états :
;
est invariante si
, soit
:
. - Pour une chaîne à deux états dont la matrice de transition n’a aucun coefficient nul, la suite
converge vers l’unique distribution invariante, quelle que soit la loi initiale.
4. Pièges classiques
- Avec la convention des lignes, on écrit
, et non
. - Le coefficient
de
compte des chaînes de longueur exactement
.
Pour aller plus loin
Besoin d’aide sur ce chapitre ?
Un blocage sur une notion, un contrôle à préparer ou le bac en ligne de mire : Pr. Elakili, agrégé de mathématiques depuis 1991, propose des cours particuliers aux lycéens (Première, Terminale, Maths expertes), en présentiel à Casablanca ou en ligne.
