Matrices et opérations
Vocabulaire et définitions
Matrice
Une matrice de taille \left(m,n\right) est un tableau de réels composé de m lignes et n colonnes, avec m et n des entiers naturels.
Matrice carrée
Une matrice carrée est une matrice possédant autant de lignes que de colonnes.
Matrice ligne
Une matrice ligne est une matrice formée d'une seule ligne.
Matrice colonne
Une matrice colonne est une matrice formée d'une seule colonne.
Matrice diagonale
Une matrice diagonale est une matrice carrée dont tous les coefficients qui ne sont pas sur la diagonale sont nuls.
Matrice nulle
Une matrice nulle est une matrice d'ordre n dont tous les coefficients sont nuls. Elle est notée 0\left(n\right).
Matrice identité
Une matrice identité est une matrice diagonale formée d'une diagonale de 1.
Deux matrices sont égales si et seulement si elles sont de même taille et leurs coefficients sont deux à deux égaux en toute position.
Somme et produit par un réel
Somme de deux matrices
Pour faire la somme de deux matrices de même format, on additionne deux à deux leurs coefficients de même position.
Produit d'une matrice par un réel
Pour multiplier une matrice par un réel, on multiplie chaque coefficient de la matrice par ce réel.
Produit de deux matrices carrées
Produit d'une matrice ligne de taille n par une matrice colonne de taille n
Soit n un entier naturel non nul.
Le produit d'une matrice ligne A=\left(a_1;\cdots;a_n\right) par une matrice colonne B=\begin{pmatrix}b_1\\\vdots\\b_n\end{pmatrix} est la matrice C à un coefficient c_{1{,}1}=a_1\times b_1+\cdots +a_n\times b_n.
Le produit de deux matrices n'existe que si le nombre de colonnes de la première est égal au nombre de lignes de la seconde.
Produit de deux matrices carrées
Le terme de position \left(i,j\right) de la matrice produit AB est égal au produit de la matrice ligne correspondant à la i -ème ligne de A par la matrice colonne correspondant de la j -ème colonne de B.
Soit n un entier naturel non nul.
Considérons les matrices carrées A, B et C de même ordre n.
\left(A+B\right)\times C=A\times C + B \times C
A\times \left(B+C\right)=A\times B + A\times C
A\times \left(B\times C\right)=\left(A\times B \right)\times C
Pour tout réel k : k\times \left(A\times B\right)=\left(k\times A \right)\times B=A\times \left(k\times B\right)
A\times I_n=I_n\times A=A, où I_n est la matrice identité d'ordre n
En général : A\times B \neq B\times A.
Inverse d'une matrice carrée
Inverse d'une matrice carrée
Une matrice carrée A d'ordre n est inversible si et seulement s'il existe une matrice B telle que AB=BA=I_n. On note cet unique inverse A^{-1}.
Écriture matricielle d'un système d'équations
La forme matricielle du système \begin{cases}ax + by = s \cr cx + dy = t\end{cases} est \begin{pmatrix}a & b \cr c & d\end{pmatrix}\begin{pmatrix}x \cr y\end{pmatrix}=\begin{pmatrix}s \cr t\end{pmatrix}.
Si \begin{pmatrix}a & b \cr c & d\end{pmatrix} est inversible, alors la matrice colonne des solutions est : \begin{pmatrix}x \cr y\end{pmatrix}=\begin{pmatrix}a & b \cr c & d\end{pmatrix}^{-1}\times\begin{pmatrix}s \cr t\end{pmatrix}.
Puissance d'une matrice carrée
Puissance d'une matrice carrée
Soit un entier naturel n non nul et une matrice carrée A.
A^n=A\times A\times A\times \cdot\cdot\cdot \times A
Pour tous entiers naturels n et m et toute matrice carrée A :
A^m \times A^n=A^{m+n}
Graphes non orientés
Vocabulaire
Graphe
On appelle graphe un ensemble de sommets, qui peuvent être reliés deux à deux par des arêtes.
Ordre d'un graphe
L'ordre d'un graphe désigne le nombre de ses sommets.
Sommets adjacents
Deux sommets d'un graphe reliés par une arête sont dits adjacents.
Degré d'un sommet
Le degré d'un sommet désigne le nombre d'arêtes dont le sommet est une extrémité.
Somme des degrés et nombre d'arêtes
La somme des degrés d'un graphe non orienté est égale au double du nombre d'arêtes que comporte ce graphe.
Matrice associée
La matrice associée (ou matrice d'adjacence) à un graphe d'ordre n est une matrice à n lignes et n colonnes, où le terme a_{i,j} est égal au nombre d'arêtes partant du sommet i vers le sommet j.
Graphe complet
Un graphe est dit complet si tous ses sommets sont deux à deux adjacents.
Chaînes
Chaîne
Une chaîne est une liste ordonnée de sommets où chaque sommet est adjacent au précédent et au suivant.
Longueur d'une chaîne
La longueur d'une chaîne désigne le nombre de ses arêtes.
Distance entre deux sommets
La distance entre deux sommets est égale à la longueur de la chaîne la plus courte reliant ces deux sommets.
Diamètre d'un graphe
Le diamètre d'un graphe est la plus grande distance entre deux sommets.
Chaîne fermée
Une chaîne fermée est une chaîne dont le premier sommet est identique au dernier sommet.
Cycle
Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.
Chaîne eulérienne
Une chaîne eulérienne est une chaîne formée de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.
Cycle eulérien
Un cycle eulérien est un cycle formé de toutes les arêtes d'un graphe, chacune n'apparaissant qu'une seule fois.
Graphe connexe
Un graphe est dit connexe si pour tout couple de sommets, il existe une chaîne reliant ces deux sommets.
Théorème d'Euler
- Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède zéro ou deux sommets de degré impair.
- Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède que des sommets de degré pair.
Nombre de chaînes de longueur p
Soit p un entier naturel non nul. On considère la matrice M^p, puissance p -ième de la matrice M associée à un graphe d'ordre n. Son terme m_{i,j} est égal au nombre de chaînes de longueur p partant du sommet i vers le sommet j.
Graphes étiquetés et pondérés
Graphes étiquetés
On appelle graphe étiqueté un graphe dont chacune des arêtes est associée à une étiquette. Une étiquette peut correspondre à un texte ou à un nombre.
Graphe pondéré
On appelle graphe pondéré un graphe étiqueté dont les étiquettes sont toutes des nombres positifs.
Poids d'une chaîne
Le poids d'une chaîne d'un graphe pondéré est la somme des poids des arêtes qui forment cette chaîne.
Plus courte chaîne
On appelle plus courte chaîne entre deux sommets une chaîne de poids minimum reliant ces deux sommets.
Graphes orientés
Graphe orienté
Un graphe orienté est un graphe dont les arêtes ont un sens.
Le terme a_{i,j} de la matrice associée à un graphe orienté est égal au nombre d'arêtes d'origine i et d'extrémité j.
Graphe probabiliste
Un graphe probabiliste est un graphe orienté pondéré où, pour chaque sommet, la somme des poids des arêtes sortantes est égale à 1.
État
Dans un graphe probabiliste, chaque sommet correspond à un état.
État probabiliste
L'état probabiliste d'un graphe probabiliste est la loi de probabilité sur l'ensemble des états. Cette loi est présentée sous la forme d'une matrice ligne, où chaque terme est égal à la probabilité de l'état correspondant.
Matrice de transition
La matrice de transition d'un graphe probabiliste d'ordre n est une matrice à n lignes et n colonnes, où le terme a_{i,j} est égal au poids de l'arête d'origine i et d'extrémité j ou à 0 si cette arête n'existe pas.
État probabiliste à l'instant n
Soient M la matrice de transition d'un graphe probabiliste d'ordre n, et P_{0} l'état initial.
La matrice ligne P_{n} de l'état probabiliste à l'instant n est égale à :
P_{n} = P_{0} \times M^{n}
État stable
Soit un graphe d'ordre n associé à une expérience donnée.
On appelle état stable un état probabiliste qui n'évolue pas lors de la répétition de l'expérience.
Soit M la matrice de transition d'un graphe probabiliste d'ordre 2.
Si M ne contient pas de 0, alors :
- L'état P_n à l'étape n converge vers un état P indépendant de l'état initial P_0.
- P est l'unique de solution de l'équation P\times M=P.