Matrices et graphes Fiche bac

I

Matrices et opérations

A

Vocabulaire et définitions

Matrice

Une matrice de taille \(\displaystyle{\left(m,n\right)}\) est un tableau de réels composé de \(\displaystyle{m}\) lignes et \(\displaystyle{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 \(\displaystyle{n}\) dont tous les coefficients sont nuls. Elle est notée \(\displaystyle{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.

B

Somme et produit par un réel

Somme de deux matrices

Pour sommer 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.

C

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 \(\displaystyle{A=\left(a_1;\cdots;a_n\right)}\) par une matrice colonne \(\displaystyle{B=\begin{pmatrix}b_1\\\vdots\\b_n\end{pmatrix}}\) est la matrice C à un coefficient \(\displaystyle{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 \(\displaystyle{\left(i,j\right)}\) de la matrice produit \(\displaystyle{AB}\) est égal au produit de la matrice ligne correspondant à la \(\displaystyle{i}\) -ème ligne de \(\displaystyle{A}\) par la matrice colonne correspondant de la \(\displaystyle{j}\) -ème colonne de \(\displaystyle{B}\).

Soit n un entier naturel non nul.

Considérons les matrices carrées \(\displaystyle{A}\), \(\displaystyle{B}\) et \(\displaystyle{C}\) de même ordre \(\displaystyle{n}\).

\(\displaystyle{\left(A+B\right)\times C=A\times C + B \times C}\)

\(\displaystyle{A\times \left(B+C\right)=A\times B + A\times C}\)

\(\displaystyle{A\times \left(B\times C\right)=\left(A\times B \right)\times C}\)

Pour tout réel \(\displaystyle{k}\) : \(\displaystyle{k\times \left(A\times B\right)=\left(k\times A \right)\times B=A\times \left(k\times B\right)}\)

\(\displaystyle{A\times I_n=I_n\times A=A}\), où \(\displaystyle{I_n}\) est la matrice identité d'ordre \(\displaystyle{n}\)

En général : \(\displaystyle{A\times B \neq B\times A}\).

II

Inverse d'une matrice carrée

Inverse d'une matrice carrée

Une matrice carrée \(\displaystyle{A}\) d'ordre \(\displaystyle{n}\) est inversible si et seulement s'il existe une matrice \(\displaystyle{B}\) telle que \(\displaystyle{AB=BA=I_n}\). On note cet unique inverse \(\displaystyle{A^{-1}}\).

Écriture matricielle d'un système d'équations

La forme matricielle du système \(\displaystyle{\begin{cases}ax + by = s \cr cx + dy = t\end{cases}}\) est \(\displaystyle{\begin{pmatrix}a & b \cr c & d\end{pmatrix}\begin{pmatrix}x \cr y\end{pmatrix}=\begin{pmatrix}s \cr t\end{pmatrix}}\).

Si \(\displaystyle{\begin{pmatrix}a & b \cr c & d\end{pmatrix}}\) est inversible, alors la matrice colonne des solutions est : \(\displaystyle{\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}}\).

III

Puissance d'une matrice carrée

Puissance d'une matrice carrée

Soit un entier naturel \(\displaystyle{n}\) non nul et une matrice carrée \(\displaystyle{A}\).

\(\displaystyle{A^n=A\times A\times A\times \cdot\cdot\cdot \times A}\)

Pour tous entiers naturels \(\displaystyle{n}\) et \(\displaystyle{m}\) et toute matrice carrée \(\displaystyle{A}\) :

\(\displaystyle{A^m \times A^n=A^{m+n}}\)

IV

Graphes non orientés

A

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 \(\displaystyle{n}\) est une matrice à \(\displaystyle{n}\) lignes et \(\displaystyle{n}\) colonnes, où le terme \(\displaystyle{a_{i,j}}\) est égal au nombre d'arêtes partant du sommet \(\displaystyle{i}\) vers le sommet \(\displaystyle{j}\).

Graphe complet

Un graphe est dit complet si tous ses sommets sont deux à deux adjacents.

B

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 \(\displaystyle{p}\)

Soit p un entier naturel non nul. On considère la matrice \(\displaystyle{M^p}\), puissance \(\displaystyle{p}\) -ième de la matrice \(\displaystyle{M}\) associée à un graphe d'ordre \(\displaystyle{n}\). Son terme \(\displaystyle{m_{i,j}}\) est égal au nombre de chaînes de longueur \(\displaystyle{p}\) partant du sommet \(\displaystyle{i}\) vers le sommet \(\displaystyle{j}\).

V

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.

VI

Graphes orientés

Graphe orienté

Un graphe orienté est un graphe dont les arêtes ont un sens.

-

Le terme \(\displaystyle{a_{i,j}}\) de la matrice associée à un graphe orienté est égal au nombre d'arêtes d'origine \(\displaystyle{i}\) et d'extrémité \(\displaystyle{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 \(\displaystyle{n}\) est une matrice à \(\displaystyle{n}\) lignes et \(\displaystyle{n}\) colonnes, où le terme \(\displaystyle{a_{i,j}}\) est égal au poids de l'arête d'origine \(\displaystyle{i}\) et d'extrémité \(\displaystyle{j}\) ou à 0 si cette arête n'existe pas.

État probabiliste à l'instant \(\displaystyle{n}\)

Soient \(\displaystyle{M}\) la matrice de transition d'un graphe probabiliste d'ordre \(\displaystyle{n}\), et \(\displaystyle{P_{0}}\) l'état initial.
La matrice ligne \(\displaystyle{P_{n}}\) de l'état probabiliste à l'instant \(\displaystyle{n}\) est égale à :

\(\displaystyle{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 \(\displaystyle{P_n}\) à l'étape n converge vers un état P indépendant de l'état initial \(\displaystyle{P_0}\).
  • P est l'unique de solution de l'équation \(\displaystyle{P\times M=P}\).