Pour construire la matrice d'adjacence M d'un graphe, on liste sommet par sommet les arêtes qui les relient entre eux.
Une matrice d'adjacence à la puissance n permet de connaître le nombre de chemins de longueurs n entre n'importe quel couple de point du graphe.
On considère le graphe suivant :
Construire sa matrice d'adjacence M puis déterminer le nombre de chaînes de longueur 3 reliant les sommets A et C.
Ranger les sommets dans l'ordre
On range les sommets dans un ordre déterminé.
- Si les sommets sont des lettres, on les range de préférence dans l'ordre alphabétique.
- Si ce sont des numéros, on les range dans l'ordre croissant.
On range les sommets dans l'ordre alphabétique : A, B, C, D.
Construire la matrice M vide
On construit la matrice vide en associant à chaque ligne et à chaque colonne un sommet, en respectant l'ordre déterminé précédemment.
On construit la matrice vide, en notant les en-têtes des lignes et des colonnes.
M = \begin{pmatrix} & A & B & C &D \cr\cr A & & & & \cr\cr B & & & & \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}
Remplir la matrice M ligne par ligne
Pour chaque ligne, on complète colonne par colonne :
- Si le sommet associé à cette ligne est relié (en étant le point de départ de l'arrête dans le cas d'un graphe orienté), au sommet associé à la colonne, on marque le chiffre 1.
- Sinon on marque le chiffre 0.
La première ligne correspond aux arêtes partant du sommet A :
- Il n'y a pas de boucle en A : on note donc 0 sur la première colonne.
- Il y en a une vers B : on note donc 1 sur la deuxième colonne.
- Il y en a une vers C : on note donc 1 sur la troisième colonne.
- Il y en a une vers D : on note donc 1 sur la dernière colonne.
On obtient :
M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & & & & \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}
La deuxième ligne correspond aux arêtes partant du sommet B :
- Il y en a une vers A : on note donc 1 sur la première colonne.
- Il y en a une vers D : on note donc 1 sur la dernière colonne.
On note 0 au niveau des autres colonnes.
On obtient :
M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}
La troisième ligne correspond aux arêtes partant du sommet C :
- Il y en a une vers A : on note donc 1 sur la première colonne.
- Il y en a une vers elle-même : on note donc 1 sur la troisième colonne.
On note 0 au niveau des autres colonnes.
On obtient :
M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & 1& 0& 1& 0\cr\cr D & & & & \end{pmatrix}
La dernière ligne correspond aux arêtes partant du sommet D :
- Il y en a une vers A : on note donc 1 sur la première colonne.
- Il y en a une vers B : on note donc 1 sur la deuxième colonne.
On note 0 au niveau des autres colonnes.
Finalement, on obtient la matrice d'adjacence M :
M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & 1& 0& 1& 0\cr\cr D & 1& 1& 0&0 \end{pmatrix}
Calculer M^n
Afin de trouver le nombre de chaînes possibles de longueur n reliant deux points d'un graphe, on doit préalablement calculer M^n.
Sauf mention contraire de l'énoncé, on peut effectuer le calcul de M^n à la calculatrice.
On cherche le nombre de chemins de longueur 3 entre les sommets A et C. On calcule donc au préalable M^3.
À l'aide la calculatrice, on obtient :
M^3 = \begin{pmatrix} 3 &4 & 4&4 \cr\cr 4& 2& 2& 3 \cr\cr 4& 2& 3& 2 \cr\cr 4& 3& 2& 2\end{pmatrix}
En déduire le nombre de chaînes de longueur n
Le nombre de chaînes de longueur n partant du sommet I et allant vers le sommet J est égal au coefficient de a_{ij} (le coefficient à l'intersection de la ligne correspondant au sommet I et de la colonne correspondant au sommet J) de la matrice M^n.
On en déduit le nombre de chemins de longueur n reliant les deux points.
Dans un graphe non orienté, le nombre de chaînes reliant I à J est égal au nombre de chemins reliant J à I, donc a_{ij}=a_{ji}.
Le nombre de chaînes de longueur 3 entre les sommets A et C est donné par le coefficient correspondant à la ligne A et à la colonne C de la matrice M^3.
M^3 = \begin{pmatrix} 3 &4 & \textcolor{Red}{4}&4 \cr\cr 4& 2& 2& 3 \cr\cr 4& 2& 3& 2 \cr\cr 4& 3& 2& 2\end{pmatrix}
Il existe donc 4 chaînes de longueur 3 reliant A à C.
Si le graphe n'est pas orienté, la matrice d'adjacence est symétrique.
La présence d'un 1 sur la diagonale de la matrice M signifie que le sommet en question est relié à lui-même.