Fiche résumé : Graphes et matrices (Terminale)

Les matrices permettent de ranger des nombres en tableau et de calculer avec ces tableaux comme avec des nombres, à quelques précautions près. Elles servent ici à compter des chemins dans un graphe, à calculer les termes de suites couplées et à prévoir l'évolution d'un système aléatoire, les chaînes de Markov.

Produit : si $A$ est $n\times p$ et $B$ est $p\times q$, $AB$ est $n\times q$ et $c_{ij}=\sum_{k=1}^{p}a_{ik}b_{kj}$ (ligne $i$ de $A$, colonne $j$ de $B$).
En général $AB\neq BA$ ; $AB=0$ n'entraîne pas $A=0$ ou $B=0$ ; $(A+B)^2=A^2+AB+BA+B^2$.
Inverse : $AB=I_n$ suffit (matrices carrées). L'inverse est unique. $(AB)^{-1}=B^{-1}A^{-1}$.
Matrice $2\times 2$ : $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ est inversible si et seulement si $ad-bc\neq 0$, et alors $A^{-1}=\dfrac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$.
Système : $AX=B$ avec $A$ inversible a pour unique solution $X=A^{-1}B$.
Si $A^2=\alpha A+\beta I$ avec $\beta\neq 0$, alors $A^{-1}=\dfrac{1}{\beta}(A-\alpha I)$.
Puissances : $A^0=I$, $A^{n+1}=A^nA$. Matrice diagonale : on élève les coefficients diagonaux à la puissance $n$. Si $A=PDP^{-1}$, alors $A^n=PD^nP^{-1}$ (récurrence).
Suites : $U_{n+1}=AU_n\Rightarrow U_n=A^nU_0$. Si $U_{n+1}=AU_n+B$ et $C=AC+B$, alors $U_n=A^n(U_0-C)+C$ ; si $I-A$ est inversible, $C=(I-A)^{-1}B$.
Graphes : ordre = nombre de sommets ; degré = nombre d'arêtes issues du sommet ; somme des degrés = $2\times$ nombre d'arêtes ; graphe complet d'ordre $n$ : $\frac{n(n-1)}{2}$ arêtes ; connexe = deux sommets toujours reliés par une chaîne.
Longueur d'une chaîne ou d'un chemin = nombre d'arêtes ou d'arcs.
Matrice d'adjacence : $m_{ij}=1$ si arête (ou arc $i\to j$), $0$ sinon ; symétrique si le graphe est non orienté.
Théorème : le coefficient $(i,j)$ de $M^n$ est le nombre de chemins de longueur $n$ de $i$ à $j$.
Chaîne de Markov : $p_{ij}=P_{(X_n=i)}(X_{n+1}=j)$ ; chaque ligne de $P$ a pour somme $1$ ; $\pi_n$ est une ligne ; $\pi_{n+1}=\pi_nP$ et $\pi_n=\pi_0P^n$.
Distribution invariante : $\pi P=\pi$ et somme des coefficients égale à $1$.
Deux états, $P=\begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}$ avec $0<a+b<2$ : $\pi=\begin{pmatrix} \frac{b}{a+b} & \frac{a}{a+b} \end{pmatrix}$ et $p_{n+1}=(1-a-b)p_n+b$, donc $(\pi_n)$ converge vers $\pi$.
Trois états (admis) : si une puissance de $P$ a tous ses coefficients strictement positifs, la distribution invariante est unique et $(\pi_n)$ converge vers elle, quelle que soit $\pi_0$.