On considère la matrice d'adjacence suivante :
A =\begin{pmatrix} 0& 1&1&1&1\cr\cr 1&1 &1&1&0\cr\cr 1&1&0&1&1 \cr\cr 1&1&1&0&1 \cr\cr 1&0&1&1&0\end{pmatrix}
Quelle est la valeur de A^3 ?
D'après la calculatrice, on obtient :
A =\begin{pmatrix} 11&13&12&12&10 \cr\cr 13&13&13&13&9 \cr\cr 12&13&11&12&10 \cr\cr 12&13&12&11&10 \cr\cr 10&9&10&10&6\end{pmatrix}
Par déduction, quel est le nombre de chemins de longueur 3 allant de B vers D ?
D'après le cours, le coefficient a_{i;j} de la matrice d'adjacence à la puissance p (c'est-à-dire A^p ) est égal au nombre de chaînes de longueur p partant du sommet i et aboutissant au sommet j.
On cherche le nombre de chaînes de longueur 3 allant de B vers D, il sera donc égal à a_{2;4}.
On remarque ici que a_{2;4} = 13, cela signifie qu'il existe 13 chaînes de longueur 3 partant du point B et aboutissant au point D.
Il existe 13 chemins de longueur 3 reliant B à D.