Une matrice d’adjacence est une matrice utilisée pour représenter les relations entre les sommets d’un graphe. Elle est fondamentale en théorie des graphes et en algèbre linéaire appliquée aux réseaux et aux systèmes connectés.
Matrice d’adjacence
Une matrice d’adjacence \( A \) pour un graphe orienté ou non orienté est une matrice carrée où l’élément \( a_{ij} \) indique la relation entre les sommets \( i \) et \( j \). Pour un graphe avec \( n \) sommets, \( A \) est de dimension \( n \times n \). Les éléments sont définis comme suit :
\[ a_{ij} = \begin{cases} 1 & \text{si une arête existe entre } i \text{ et } j, \\ 0 & \text{sinon.} \end{cases} \]
Exemples sur la Matrice d’adjacence
Prenons un graphe non orienté avec 4 sommets \( V = \{1, 2, 3, 4\} \) et les arêtes suivantes : \( \{(1, 2), (2, 3), (3, 4), (4, 1)\} \). La matrice d’adjacence correspondante est donnée par :
\[ A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \]
Pour un graphe orienté avec \( V = \{1, 2, 3\} \) et les arêtes \( \{(1, 2), (2, 3)\} \), la matrice d’adjacence est donnée par :
\[ B = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix} \]
Propriétés
- Pour un graphe non orienté, la matrice d’adjacence est symétrique.
- La somme des éléments d’une ligne donne le degré du sommet correspondant pour un graphe non orienté.
- Pour un graphe orienté, les éléments hors diagonale représentent les connexions directionnelles.
- La puissance \( A^k \) de la matrice d’adjacence donne le nombre de chemins de longueur \( k \) entre les sommets.
Méthodes sur la Matrice d’Adjacence
Pour construire une matrice d’adjacence :
- Identifiez les sommets et les arêtes du graphe.
- Attribuez une valeur de 1 à chaque élément \( a_{ij} \) si une connexion existe entre \( i \) et \( j \), et 0 sinon.
Des outils comme NetworkX ou MATLAB peuvent générer des matrices d’adjacence de manière automatisée.
Exercices pour s’entraîner
Exercice Moyenne :
- Construisez la matrice d’adjacence pour un graphe avec les sommets \( \{1, 2, 3, 4\} \) et les arêtes \( \{(1, 2), (2, 3), (3, 1)\} \).
- Déterminez si le graphe représenté par la matrice suivante est orienté ou non orienté : \[ A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \]
Exercice Difficile :
- Pour la matrice d’adjacence \( B = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} \), trouvez \( B^2 \) et interprétez son sens dans le contexte des chemins.
- Montrez que la trace de la matrice d’adjacence d’un graphe simple est toujours nulle.
Tester Vos Connaissances
Ce quiz interactif vous aidera à tester vos connaissances sur les matrices d’adjacence.
