Matrices

Définition

Définition

Soient mm et nn deux entiers non nuls. Une matrice réelle AA de taille m×nm \times n est un tableau de réels tel que :

A=(a1,1a1,2a1,na2,1a2,2a2,nam,1am,2am,n)\displaystyle{A = \begin{pmatrix}a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n}\end{pmatrix}}

a1,1a_{1,1}, a1,2a_{1,2}, a2,1a_{2,1}, ..., am,na_{m,n} sont les coefficients de la matrice. L’ensemble des matrices à coefficients réels est noté Mm,n(R)\mathcal{M}_{m,n}(\mathbb{R}).

Il serait également possible de prendre des matrices à coefficients entiers ou même complexes, mais nous nous limiterons ici au cas des matrices réelles.

Types de matrices

Selon leur taille, on peut avoir différents types de matrices :

  • Une matrice 1×n1 \times n est une matrice ligne de taille nn.

  • Une matrice m×1m \times 1 est une matrice colonne de taille mm.

  • Une matrice n×nn \times n est une matrice carrée d’ordre nn. L’ensemble de ces matrices est noté Mn(R)\mathcal{M}_n(\mathbb{R}).

  • Une matrice 1×11 \times 1 est un réel.

  • La matrice m×nm \times n dont tous les termes sont nuls est la matrice nulle et est notée 0Mm,n(R)0_{\mathcal{M}_{m,n}(\mathbb{R})} (ou plus simplement 0m,n0_{m,n}).

Types de matrices carrées

Types de matrices carrées

Il existe différentes matrices carrées remarquables :

  • Une matrice carrée dont tous les coefficients en dessous de la diagonale principale sont nuls est une matrice triangulaire supérieure.

  • Une matrice triangulaire supérieure dont les coefficients sur la diagonale sont nuls est une matrice triangulaire supérieure stricte.

  • Une matrice carrée dont tous les coefficients au-dessus de la diagonale principale sont nuls est une matrice triangulaire inférieure.

  • Une matrice triangulaire inférieure dont les coefficients sur la diagonale sont nuls est une matrice triangulaire inférieure stricte.

  • Une matrice carrée dont tous les coefficients qui ne sont pas sur la diagonale sont nuls est une matrice diagonale.

  • Une matrice diagonale dont les coefficients sont égaux à 11 est une matrice identité. Si la taille d’une telle matrice est nn, alors on la note InI_n.

Diagonale d’une matrice carrée

La diagonale d’une matrice carrée d’ordre nn représente l’ensemble des coefficients ai,ia_{i,i}ii varie de 11 à nn.

Opérations sur les matrices

Somme

Somme de deux matrices

Pour additionner deux matrices de même taille, il suffit d’additionner leurs coefficients deux-à-deux. Plus spécifiquement :

(a1,1a1,2a1,na2,1a2,2a2,nam,1am,2am,n)+(b1,1b1,2b1,nb2,1b2,2b2,nbm,1bm,2bm,n)\displaystyle{\begin{pmatrix}a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n}\end{pmatrix} + \begin{pmatrix}b_{1,1} & b_{1,2} & \dots & b_{1,n} \\ b_{2,1} & b_{2,2} & \dots & b_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{m,1} & b_{m,2} & \dots & b_{m,n}\end{pmatrix}}

=(a1,1+b1,1a1,2+b1,2a1,n+b1,na2,1+b2,1a2,2+b2,2a2,n+b2,nam,1+bm,1am,2+bm,2am,n+bm,n)\displaystyle{= \begin{pmatrix}a_{1,1} + b_{1,1} & a_{1,2} + b_{1,2} & \dots & a_{1,n} + b_{1,n} \\ a_{2,1} + b_{2,1} & a_{2,2} + b_{2,2} & \dots & a_{2,n} + b_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} + b_{m,1} & a_{m,2} + b_{m,2} & \dots & a_{m,n} + b_{m,n}\end{pmatrix}}

Attention !

Il n’est possible d’additionner que deux matrices de même taille.

Produit

Multiplication d’une matrice par un réel

Soit λ\lambda un réel. Le produit d’une matrice par λ\lambda est la matrice de même taille dont les coefficients sont tous multipliés par λ\lambda. Plus spécifiquement :

λ×(a1,1a1,2a1,na2,1a2,2a2,nam,1am,2am,n)=(λ×a1,1λ×a1,2λ×a1,nλ×a2,1λ×a2,2λ×a2,nλ×am,1λ×am,2λ×am,n)\displaystyle{\lambda \times \begin{pmatrix}a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n}\end{pmatrix} = \begin{pmatrix}\lambda \times a_{1,1} & \lambda \times a_{1,2} & \dots & \lambda \times a_{1,n} \\ \lambda \times a_{2,1} & \lambda \times a_{2,2} & \dots & \lambda \times a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda \times a_{m,1} & \lambda \times a_{m,2} & \dots & \lambda \times a_{m,n}\end{pmatrix}}

Si AA est la matrice de gauche, on note λA\lambda A la matrice de droite.

Soustraction de deux matrices

Pour soustraire deux matrices AA et BB, on additionne AA et (1)B(-1)B i.e. AB=A+(1)BA - B = A + (-1)B.

Produit d’une matrice ligne et d’une matrice colonne

Soient L=(l1...ln)L = \begin{pmatrix}l_1 & ... & l_n\end{pmatrix} une matrice ligne de taille nn et C=(c1cn)C = \begin{pmatrix}c_1 \\ \vdots \\ c_n\end{pmatrix} une matrice colonne de taille nn.

Le produit de ces deux matrices (noté LCLC) est le réel LC=l1×c1++ln×cnLC = l_1 \times c_1 + \dots + l_n \times c_n.

Plus généralement, le produit matriciel ne se limite pas qu’à la multiplication d’une matrice ligne avec une matrice colonne.

Produit de deux matrices

Soient AA une matrice de taille m×nm \times n et BB une matrice de taille n×pn \times p deux matrices. Le produit de ces deux matrices (notée A×BA \times B ou ABAB) est la matrice de taille m×pm \times p dont le coefficient à la position (i;j)(i; j) est égal au produit de la ii-ième ligne de AA par la jj-ième colonne de BB. Plus spécifiquement, en notant LiL_i la ii-ème ligne de AA et CjC_j la jj-ième colonne de BB :

AB=(c1,1c1,2c1,pc2,1c2,2c2,pcm,1cm,2cm,p)\displaystyle{AB = \begin{pmatrix}c_{1,1} & c_{1,2} & \dots & c_{1,p} \\ c_{2,1} & c_{2,2} & \dots & c_{2,p} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m,1} & c_{m,2} & \dots & c_{m,p}\end{pmatrix}}ci,j=Li×Cjc_{i,j} = L_i \times C_j.

Attention !

Le produit matriciel n’est pas commutatif ! Donc en général, ABBAAB \neq BA.

De plus, il faut bien s’assurer que le nombre de lignes de AA est égal au nombre de colonnes de BB.

Si AA et BB sont deux matrices diagonales de taille nn. Leur produit est la matrice diagonale de même taille dont le coefficient à la position (i;i)(i; i) est le produit du coefficient de AA à la position (i;i)(i;i) par celui du coefficient de BB à la position (i;i)(i;i). Plus spécifiquement, en notant A=(ai,j)A = (a_{i,j}) et B=(bi,j)B = (b_{i,j}) :

(a1,1000a2,2000an,n)×(b1,1000b2,2000bn,n)\displaystyle{\begin{pmatrix}a_{1,1} & 0 & \dots & 0 \\ 0 & a_{2,2} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & a_{n,n}\end{pmatrix} \times \begin{pmatrix}b_{1,1} & 0 & \dots & 0 \\ 0 & b_{2,2} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & b_{n,n}\end{pmatrix}}

=(a1,1×b1,1000a2,2×b2,2000an,n×bn,n)\displaystyle{= \begin{pmatrix}a_{1,1} \times b_{1,1} & 0 & \dots & 0 \\ 0 & a_{2,2} \times b_{2,2} & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & a_{n,n} \times b_{n,n}\end{pmatrix}}

De plus, on a AB=BAAB = BA.

Propriétés du produit matriciel

Soient AA, BB et CC trois matrices carrées d’ordre nn. Alors :

  • Le produit matriciel est associatif : A(BC)=(AB)CA(BC) = (AB)C.

  • Le produit matriciel est distributif : A(B+C)=AB+ACA(B + C) = AB + AC.

  • InI_n est l’unité de Mn(R)\mathcal{M}_{n}(\mathbb{R}) : AIn=InA=AAI_n = I_nA = A.

  • 0n0_n est le zéro de Mn(R)\mathcal{M}_{n}(\mathbb{R}) : A0n=0nA=0nA0_n = 0_nA = 0_n et A+0n=AA + 0_n = A.

  • Pour tout λR\lambda \in \mathbb{R}, λ(AB)=(λA)B=A(λB)\lambda (AB) = (\lambda A)B = A(\lambda B).

Attention !

Si on a une égalité du type A×B=0A \times B = 0, cela n’implique pas forcément que A=0A = 0 ou B=0B = 0 !

De plus, si on a AB=ACAB = AC, on n’a pas forcément B=CB = C.

Cela peut sembler logique, mais on signale tout de même que les priorités les opératoires sont les mêmes que dans les ensembles de nombres comme R\mathbb{R} ou C\mathbb{C} (la multiplication prime sur l’addition, etc...).

Inverse et déterminant

Inverse d’une matrice

Soit AA une matrice carrée d’ordre nn. AA est dite inversible s’il existe une matrice A1A^{-1} telle que A×A1=InA \times A^{-1} = I_n.

Si cette matrice existe, elle est unique et s’appelle inverse de AA. De plus, AA et A1A^{-1} commutent.

Le déterminant permet, entre autres, de calculer l’inverse d’une matrice (s’il existe). Nous nous limiterons ici au cas des matrices carrées d’ordre 22, mais il est possible de le généraliser encore plus.

Déterminant d’une matrice 2×22 \times 2

Soit A=(abcd)\displaystyle{A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}} une matrice carrée d’ordre 22.

Alors le déterminant de AA (noté det(A)\det(A)) est le réel det(A)=adbc\det(A) = ad - bc. De plus, AA est inversible si et seulement si det(A)0\det(A) \neq 0.

Inverse d’une matrice 2×22 \times 2

Soit A=(abcd)\displaystyle{A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}} une matrice carrée d’ordre 22 dont le déterminant ne s’annule pas.

Alors A1=1det(A)(dbca)\displaystyle{A^{-1} = \frac{1}{\det(A)} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}}.

Exemple

Calculons le produit de A=(2164)\displaystyle{A = \begin{pmatrix}2 & 1 \\ 6 & 4\end{pmatrix}} par B=(4162)\displaystyle{B = \begin{pmatrix}4 & -1 \\ -6 & 2\end{pmatrix}}, et déduisons-en que AA est inversible sans utiliser la formule donnée précédemment.

Le produit nous donnera une matrice carrée d’ordre 22 car on multiplie deux matrices carrées d’ordre 22 :

(2164)×(4162)=(862+224246+8)=(2002)\displaystyle{\begin{pmatrix} 2 & 1 \\ 6 & 4 \end{pmatrix} \times \begin{pmatrix} 4 & -1 \\ -6 & 2\end{pmatrix} = \begin{pmatrix}8-6 & -2+2 \\ 24-24 & -6+8 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}}

Donc A×B=2I2A \times B = 2I_2. Ainsi, AA est inversible et A1=12BA^{-1} = \frac{1}{2} B.

Puissance

Puissance d’une matrice carrée

Soient AA une matrice carrée d’ordre nn et ii un entier naturel :

  • Si i>0i > 0, Ai=A××Ai fois=Ai1×A\displaystyle{A^i = \underbrace{A \times \dots \times A}_{i \text{ fois}} = A^{i-1} \times A}.

  • Si i=0i = 0, Ai=A0=InA^i = A^0 = I_n.

  • Si i<0i < 0, Ai=A1××A1i fois=Ai1×A1\displaystyle{A^i = \underbrace{A^{-1} \times \dots \times A^{-1}}_{i \text{ fois}} = A^{i-1} \times A^{-1}}.

De plus, pour tout entier naturel jj, on a Ai×Aj=Ai+jA^i \times A^j = A^{i+j}.

Puissance d’une matrice diagonale

Si AA est une matrice diagonale, alors AiA^i est la matrice de même taille où tous les termes de la diagonale sont mis à la puissance ii (cela vaut aussi si ii est négatif et que la diagonale ne comporte pas de 00).

Transposition

Définition

Soit AA une matrice. La matrice transposée de AA (notée tA^tA) est la matrice dont la ii-ième ligne correspond à la ii-ième colonne de AA.

Exemple

Soient A=(2593610)\displaystyle{A = \begin{pmatrix} 2 & 5 & 9 \\ 3 & 6 & 10 \end{pmatrix}} et B=(01123581321)\displaystyle{B = \begin{pmatrix} 0 & 1 & 1 \\ 2 & 3 & 5 \\ 8 & 13 & 21 \end{pmatrix}}. Calculons tA^tA et tB^tB.

On a tA=(2356910)\displaystyle{^tA = \begin{pmatrix} 2 & 3 \\ 5 & 6 \\ 9 & 10 \end{pmatrix}} et tB=(02813131521)\displaystyle{^tB = \begin{pmatrix} 0 & 2 & 8 \\ 1 & 3 & 13 \\ 1 & 5 & 21 \end{pmatrix}}.

Applications

Écriture matricielle d’un système d’équations linéaires

Lien entre système d’équations linéaires et matrices

Soient quatre réels aa, bb, cc et dd et soient deux réels α\alpha et β\beta. Le système d’équations linéaires à deux inconnues (S):{ax+by=αcx+dy=β\displaystyle{(S) : \begin{cases}ax + by = \alpha \\ cx + dy = \beta\end{cases}} (d’inconnues xx et yy) peut s’écrire matriciellement :

(S)    (abcd)=A(xy)=X=(αβ)=B\displaystyle{(S) \iff \underbrace{\begin{pmatrix}a & b \\ c & d\end{pmatrix}}_{= \, A} \underbrace{\begin{pmatrix}x \\ y\end{pmatrix}}_{= \, X} = \underbrace{\begin{pmatrix}\alpha \\ \beta\end{pmatrix}}_{= \, B}}

Résolution du système (S)(S)

Avec les notations ci-dessus, si AA est inversible (voir les paragraphes suivants) alors le système (S)(S) admet une unique solution X=A1BX = A^{-1}B.

Exemple

Cela peut sembler compliqué à appliquer, mais il n’en est rien !

Par exemple, transformons le système (S):{x+2y=12x+5y=4\displaystyle{(S) : \begin{cases}x + 2y = 1 \\ 2x + 5y = 4 \end{cases}} en une égalité de matrices :

(S)    (1225)(xy)=(14)\displaystyle{(S) \iff \begin{pmatrix}1 & 2 \\ 2 & 5\end{pmatrix} \begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}1 \\ 4 \end{pmatrix}}

Or l’inverse de (1225)\displaystyle{\begin{pmatrix}1 & 2 \\ 2 & 5\end{pmatrix}} est (5221)\displaystyle{\begin{pmatrix}5 & -2 \\ -2 & 1\end{pmatrix}}. D’où (xy)=(5221)(14)=(32)\displaystyle{\begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix}5 & -2 \\ -2 & 1\end{pmatrix} \begin{pmatrix}1 \\ 4\end{pmatrix} = \begin{pmatrix}-3 \\ 2\end{pmatrix}}.

Or deux matrices sont égales si et seulement si leurs coefficients sont tous égaux. Donc on a x=3x = -3 et y=2y = 2.

Nous avons travaillé ici avec un système de deux équations, mais il est tout à fait possible de généraliser cette méthode à plus de deux équations !

Suites de matrices colonnes

Soit (Un)(U_n) une suite de matrices colonnes de taille mm vérifiant une relation du type Un+1=AUnU_{n+1} = A U_n pour tout nNn \in \mathbb{N} et où AMm(R)A \in \mathcal{M}_m(\mathbb{R}).

Alors, pour tout nNn \in \mathbb{N}, Un=AnU0U_n = A^n U_0.

Il peut sembler étrange de manipuler des suites de matrices, mais c’est en réalité très intuitif. Par exemple, définissions la suite (Un)(U_n) par U0=(12)\displaystyle{U_0 = \begin{pmatrix} 1 \\ 2 \end{pmatrix}} et pour tout n1n \geq 1 par Un+1=(1002)=AUn\displaystyle{U_{n+1} = \underbrace{\begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}}_{= A} U_n} et cherchons son terme général.

Par la formule précédente, pour tout nNn \in \mathbb{N}, Un=AnU0U_n = A^n U_0. Or, AA est une matrice diagonale, donc An=(1n002n)\displaystyle{A^n = \begin{pmatrix} 1^n & 0 \\ 0 & 2^n \end{pmatrix}}, et ainsi :

Un=(1002n)(12)=(12n+1)\displaystyle{U_n = \begin{pmatrix} 1 & 0 \\ 0 & 2^n \end{pmatrix} \begin{pmatrix} 1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 \\ 2^{n+1} \end{pmatrix}}

On remarque en particulier que la suite (Un)(U_n) est divergente (à cause de sa deuxième coordonnée qui tend vers ++\infty).

Soit (Vn)(V_n) une suite de matrices colonnes de taille mm vérifiant une relation du type Vn+1=AVn+BV_{n+1} = A V_n + B pour tout nNn \in \mathbb{N} et où AA, BMm(R)B \in \mathcal{M}_m(\mathbb{R}). Supposons qu’il existe une matrice XMm(R)X \in \mathcal{M}_m(\mathbb{R}) telle que AX+B=XAX + B = X.

Alors, pour tout nNn \in \mathbb{N}, Un=An(U0X)+XU_n = A^n (U_0 - X) + X.

Transformations géométriques du plan

Il est possible de faire le lien entre les matrices et certains types de transformations géométriques du plan.

On se place dans un repère (O;i,j)(O; \overrightarrow{i}, \overrightarrow{j}). Soient A=(xA;yA)A = (x_A; y_A) et B=(xB;yB)B = (x_B; y_B) deux points du plan.

  • BB est l’image de AA par la translation de vecteur u=(xuyu)\displaystyle{\overrightarrow{u} = \begin{pmatrix} x_{\overrightarrow{u}} \\ y_{\overrightarrow{u}} \end{pmatrix}} si et seulement si (xByB)=(xuyu)+(xAyA)\displaystyle{\begin{pmatrix} x_B \\ y_B \end{pmatrix} = \begin{pmatrix} x_{\overrightarrow{u}} \\ y_{\overrightarrow{u}} \end{pmatrix} + \begin{pmatrix} x_A \\ y_A \end{pmatrix}}.

  • BB est l’image de AA par la rotation de centre OO et d’angle θR\theta \in \mathbb{R} si et seulement si (xByB)=(cos(θ)sin(θ)sin(θ)cos(θ))(xAyA)\displaystyle{\begin{pmatrix} x_B \\ y_B \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{pmatrix} \begin{pmatrix} x_A \\ y_A \end{pmatrix}}.

Exemple

On pose A=(1;1)A = (1; 1). Calculons les coordonnées de BB qui est l’image de AA par la translation de vecteur u=(12)\displaystyle{\overrightarrow{u} = \begin{pmatrix} -1 \\ -2 \end{pmatrix}}, et de CC qui est l’image de AA par la rotation de centre OO et d’angle π4\displaystyle{\frac{\pi}{4}}.

On a :

(xByB)=(12)+(11)\displaystyle{\begin{pmatrix} x_B \\ y_B \end{pmatrix} = \begin{pmatrix} -1 \\ -2 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \end{pmatrix}} et (xCyC)=(22222222)(11)\displaystyle{\begin{pmatrix} x_C \\ y_C \end{pmatrix} = \begin{pmatrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix}}.

Donc B=(1;1)B = (-1; 1) et C=(0;2)C = (0; \sqrt{2}).

Graphes

Graphes non-orientés et orientés

Graphe non-orienté

Un graphe GG non-orienté est un couple (S;A)(S; A) où :

  • SS est l’ensemble des sommets de GG.

  • AA est un ensemble contenant les éléments de la forme {si;sj}\{s_i; s_j\}sis_i, sjSs_j \in S, et correspond aux arêtes de GG.

Exemple

Par exemple, G=({A;B;C;D;E},{{A;B};{B;C};{C;D};{D;A};{D;E};{E;A}}G = (\{A; B; C; D; E\}, \{\{A; B\}; \{B; C\}; \{C; D\}; \{D; A\}; \{D; E\}; \{E; A\}\} est un graphe non-orienté que l’on peut représenter comme tel : image Signalons tout de même que l’ordre dans lequel on relie les sommets n’a pas d’importance.

Graphe orienté

Un graphe GG orienté est un couple (S;A)(S; A) où :

  • SS est l’ensemble des sommets de GG.

  • AA est un sous-ensemble de S×SS \times S, et correspond aux arêtes orientées de GG.

Exemple

Par exemple, G=({A;B;C;D;E},{(A;B);(B;C);(C;D);(D;E);(A;E)}G = (\{A; B; C; D; E\}, \{(A; B); (B; C); (C; D); (D; E); (A; E)\} est un graphe orienté que l’on peut représenter comme tel : image

À noter que dans les deux cas, il est possible de relier un sommet à lui-même (en faisant une boucle).

Définition

Soit G=(S;A)G = (S; A) un graphe. Donnons quelques définitions nécessaires pour la suite :

  • L’ordre de GG est le nombre de sommets que possède GG (i.e. le cardinal de SS).

  • Le degré d’un sommet est le nombre d’arêtes qui passent par ce sommet (quelque-soit le sens de l’arête dans le cas où GG est orienté). Les boucles comptent pour 22.

  • Un sommet AA est adjacent à un autre sommet BB s’il existe une arête reliant AA à BB (i.e. si (A;B)A(A; B) \in A dans le cas où GG est orienté / si (A;B)(A; B) ou (B;A)A(B; A) \in A si GG n’est pas orienté). Si AA n’est adjacent à aucun autre sommet, alors AA est un sommet isolé.

  • GG est dit complet si tout sommet de AA est adjacent à chacun des autres.

Soit GG un graphe. On note par aa son nombre d’arêtes, et par dd la somme des degrés de ses sommets. Alors d=2ad = 2a.

Exemple

On considère le graphe orienté GG suivant : image Alors :

  • GG n’est pas complet.

  • L’ordre de GG est égal à 55.

  • GG a 44 arêtes (donc la somme des degrés des sommets de GG vaut 2×4=82 \times 4 = 8).

  • Le degré des sommets AA et BB est égal à 11.

  • Le degré des sommets CC, DD et EE est égal à 22.

  • Le sommet AA est adjacent au sommet EE (mais EE n’est pas adjacent à AA).

  • CC est un sommet isolé.

  • L’arête orientée qui va de CC à CC est une boucle.

Chaînes et chemins

Définition

Soit GG un graphe non-orienté. On appelle chaîne de taille nn, toute succession de nn arêtes de GG telle que l’extrémité de chacune est l’origine de la suivante.

Si GG est un graphe orienté, on parle de chemin plutôt que de chaîne.

Définition

Dans un graphe GG non-orienté :

  • Si l’origine d’une chaîne coïncide avec sa fin, on parle de chaîne fermée (ou de chemin fermé si GG est orienté).

  • Si la chaîne est composée d’arêtes toutes distinctes, on parle de cycle (ou de circuit si GG est orienté).

Exemple

On considère le graphe non-orienté suivant : image Alors :

  • ABCDAA-B-C-D-A est un chemin fermé de longueur 44 (c’est même un cycle).

  • ACBDA-C-B-D est un chemin de longueur 33 reliant AA à DD (mais il y en a beaucoup d’autres).

Matrices d’adjacence

Le but de cette section est d’étudier le lien étroit qui relie les matrices et les graphes.

Définition

Soit G=(S;A)G = (S; A) un graphe d’ordre nn. On note S={s1,,sn}S = \{s_1, \dots, s_n\} l’ensemble des sommets de GG.

On fait correspondre à GG la matrice carrée d’ordre nn dont le coefficient à la ligne ii et la colonne jj est égal au nombre d’arêtes reliant le sommet sis_i au sommet sjs_j. Cette matrice est appelée matrice d’adjacence du graphe GG.

On notera qu’une telle matrice est symétrique (par rapport à sa diagonale) si le graphe en question est non-orienté.

Exemple

On considère le graphe orienté G1G_1 suivant : image Sa matrice d’adjacence est la matrice M1=(010001100)\displaystyle{M_1 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}}.

Exemple

On considère le graphe non-orienté G2G_2 suivant (i.e. le même que le G1G_1 mais sans les orientations) : image Sa matrice d’adjacence est la matrice M2=(011101110)\displaystyle{M_2 = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}}.

Remarquons sur ces deux exemples que le caractère orienté ou non d’un graphe change sa matrice d’adjacence !

Nombre de chemins de longueur kk

Soient G=(S;A)G = (S; A) un graphe orienté d’ordre nn et MM sa matrice d’adjacence. On note S={s1,,sn}S = \{s_1, \dots, s_n\} l’ensemble des sommets de GG.

Alors le coefficient à la ligne ii et à la colonne jj de MkM^k est le nombre de chemins de longueur kk reliant le sommet sis_i au sommet sjs_j.

Démonstration

Vous avez aimé ce cours ?

Faîtes-le nous savoir dans les commentaires !

Avatar (prévisualisation)
avatar

Skyost Modérateur

Oulà oui ! C'est corrigé, merci beaucoup 😁

16/07/2021 13:29:42
avatar

moi

Il y a une erreur sur le déterminant des matrices 2*2

15/07/2021 16:34:50