Les graphes ont récemment fait leur entrée dans le programme de maths appliquées. C’est désormais un pilier de ce dernier, puisqu’on peut voir qu’ils sont déjà présents dans Ecricome 2023, ou encore dans le sujet 0 de HEC 2023. Il est donc important que tu comprennes bien les liens existants entre les graphes et leurs matrices d’adjacence.
Le mécanisme de passage entre graphe et matrice d’adjacence
Considérons un graphe d’ordre \( n \in \mathbb{N*} \). On numérote les sommets de \(1 \ \text{à} \ n\).
On appelle matrice d’adjacence associée à ce graphe la matrice \(A\) dont le terme \(a_{i,j} \) vaut \(1\) si les sommets \(i\) et \(j\) sont reliés par une arête (dans le sens où \(i\) est l’origine, et \(j\) est le sommet vers lequel la flèche est pointée) et \(0\) sinon.
On tire premièrement de cette description que la matrice d’adjacence d’un graphe d’ordre \(n\) est forcément de taille \( n \times n \).
Dans le cas d’un graphe non orienté, les coefficients \(a_{i,j} \) \ et \ \(a_{j,i} \) sont égaux pour tout \(i\) et tout \(j\) compris entre \(1\) et \(n\). De fait, si le sommet \(i\) « pointe » vers le sommet \(j\), alors forcément le sommet \(j\) « pointe » lui aussi vers le sommet \(i\). On en tire que la matrice d’adjacence d’un graphe non orienté est forcément symétrique.
Dans le cas d’un graphe orienté cependant, la matrice d’adjacence n’est pas a priori symétrique.
Exemples d’un graphe à une matrice d’adjacence
Considérons le graphe suivant :
Ce graphe est orienté, et sa matrice d’adjacence est la matrice \( A = \begin{pmatrix} 0 & 1 & 1 & 0
\\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \)
Il faut bien comprendre dans un graphe orienté que le coefficient \( a_{i,j} \) prend la valeur 1 si et seulement si le sommet \(i\) « pointe » vers le sommet \(j\).
De fait, le sommet 1 relie le sommet 2 par une arête, ce qui explique que le coefficient \( a_{1,2} \) vaille 1. De même, le sommet 2 relie le sommet 3 par une arête, donc le coefficient \( a_{2,3} \) vaut également 1.
Prenons à présent le même graphe, mais cette fois-ci, non orienté. On a donc :
Ce graphe est non orienté, et sa matrice d’adjacence est la matrice \( A = \begin{pmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} \)
On voit en premier lieu que la matrice est bien symétrique. De même, on peut garder la même définition que précédemment, puisqu’un graphe non orienté n’est rien d’autre qu’un graphe… « orienté par les deux bouts », c’est-à-dire qu’on peut aussi le représenter comme un graphe orienté dont les arêtes « pointeraient » à la fois vers le sommet \(i\) et vers le sommet \(j\).
De fait, on voit que 1 pointe vers 2 et que donc 2 pointe vers 1. Ainsi, les coefficients \( a_{1,2} \) et \( a_{2,1} \) valent chacun 1.
Exemples d’une matrice d’adjacence à un graphe
Prenons par exemple la matrice d’adjacence \( A = \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} \)
On a alors le graphe suivant :
De fait, on voit que dans la matrice, les coefficients \(a_{1,3}\) et \( a_{3,1}\) valent 1, ce qui explique qu’une arête parte de 1 pour aller vers 3, et qu’une arête parte de 3 pour aller vers 1.
C’est en utilisant cette définition qu’on se rend compte qu’on pourrait tout à fait représenter ce graphe non orienté sous la forme d’un graphe orienté (même si la matrice d’adjacence est symétrique : rien n’empêche un graphe orienté d’avoir une matrice symétrique !). Dans ce cas, on aurait :
Propriétés sur les liens entre un graphe et sa matrice d’adjacence
Reprenons les propriétés évoquées plus haut et ajoutons-en quelques-unes. On prend ici un graphe \( \mathcal{G} \) admettant une matrice d’adjacence \(A\).
1 – La matrice d’adjacence d’un graphe d’ordre \(n\) est forcément de taille \( n \times n \).
2 – La matrice d’adjacence d’un graphe non orienté est symétrique.
3 – Une matrice d’adjacence d’un graphe sera toujours binaire, c’est-à-dire formellement que : \(a_{i,j} \in [0,1], \forall (i,j) \in [1,n]^{2} \).
4 – Le coefficient diagonal \(a_{i,i} \) vaudra 1 si et seulement s’il existe une boucle sur le sommet \(i\).
5 – Pour un graphe simple non orienté, les degrés des sommets s’obtiennent en sommant les coefficients des lignes d’une matrice d’adjacence. Formellement : \( \forall i \in [1, n], \text{deg}(s_i) = \displaystyle \sum_{k=1}^{n} a_{i,k} \).
6 – Le terme \(a_{i,j}\) \ de la matrice \(A^{k}\) est le nombre de chaînes de longueur \(k\) reliant le sommet \(i\) au sommet \(j\), \(k\) étant un entier naturel non nul.
7 – \( \mathcal{G} \) est connexe si et seulement si la matrice \( I_n + A + A^{2} … + A^{n-1} \) est à coefficient strictement positif.
Exemples
Nous allons ici revenir sur les propriétés n° 5, n° 6 et n° 7. Si tu ne sais pas ce qu’est une chaîne, ou si tu ne connais pas le principe de connexité, regarde le cours sur les graphes.
Propriété n° 5
Reprenons le graphe simple non orienté précédemment étudié, qui avait pour matrice d’adjacence \( A = \begin{pmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} \).
Pour le degré du sommet n° 1 par exemple, on somme les coefficients de la ligne n° 1 et on obtient que \(deg(S_1) = 2 \), puis en sommant les coefficients des autres lignes, on a que \(deg(S_2) = 3 \), \(deg(S_3) = 3 \), et \(deg(S_4) = 2 \).
Propriété n° 6
Cette propriété très utile fonctionne que \( \mathcal{G} \) soit un graphe orienté ou non orienté. Reprenons le graphe suivant :
On suppose que l’énoncé demande de dénombrer le nombre de chaînes de longueur 3 partant du sommet 1 pour aller au sommet 4. On rappelle que la matrice d’adjacence de ce graphe est \( A = \begin{pmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} \).
Après calculs, \( A^{3} = \begin{pmatrix} 2 & 5 & 5 & 2 \\ 5 & 4 & 5 & 5 \\ 5 & 5 & 4 & 5 \\ 2 & 5 & 5 & 2 \end{pmatrix} \).
Il suffit alors de lire le coefficient \(a_{1,4}\) de cette nouvelle matrice, qui vaut 2. On peut aussi voir par exemple qu’il y a cinq chaînes de longueur 3 reliant les sommets 1 et 2.
Propriété n° 7
On rappelle qu’un graphe est connexe si et seulement si pour n’importe quels sommets \(i\) et \(j\), il existe une chaîne reliant \(i\) et \(j\). Par exemple, prenons le graphe suivant :
Il a pour matrice d’adjacence la matrice \(A = \begin{pmatrix} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{pmatrix} \).
On calcule \(A^{1}, A^{2}, A^{3}, A^{4} \), puis on additionne toutes ces matrices, suivies de la matrice \( I_{5} \). On obtient alors une matrice à coefficients strictement positifs, puisque, avant même d’ajouter \(A^{4}\), on obtient déjà la matrice \(I_{5} + A^{1} + A^{2} + A^{3}= \begin{pmatrix} 3 & 2 & 5 & 2 & 3 \\ 2 & 5 & 6 & 5 & 1 \\ 5 & 6 & 6 & 6 & 1 \\ 2 & 5 & 6 & 5 & 1 \\ 3 & 1 & 1 & 1 & 2 \end{pmatrix} \).
Ainsi, le graphe précédemment donné est bien connexe.
Conclusion
Tu as pu le voir, il existe de nombreux liens entre un graphe et sa matrice d’adjacence. La technique principale que tu dois retenir est le passage de l’un à l’autre, mais il est essentiel de te rappeler aussi tous les liens secondaires qu’il existe entre ces objets, car ce sont des objets d’études très courants, présents dans de nombreux exercices, et qui sont déjà tombés aux concours.
Tu peux retrouver nos autres ressources mathématiques ici.
