On considère la matrice d'adjacence suivante :

A =\begin{pmatrix} 0& 1&1&1 \cr\cr 1&0 &0&1\cr\cr 1&0&0&0\cr\cr 1&1&0&0\end{pmatrix}

Quelle est la valeur de A^2 ?

A ^2=\begin{pmatrix} 1& 1&0&3 \cr\cr 1&2 &2&1\cr\cr 0&1&1&2\cr\cr 1&1&1&2\end{pmatrix}

A ^2=\begin{pmatrix} 3& 2&1&1 \cr\cr 1&2 &1&1\cr\cr 0&1&1&1\cr\cr 1&1&1&2\end{pmatrix}

A ^2=\begin{pmatrix} 3& 1&1&1 \cr\cr 1&2 &2&1\cr\cr 0&1&1&3\cr\cr 1&1&1&2\end{pmatrix}

A ^2=\begin{pmatrix} 3& 1&0&1 \cr\cr 1&2 &1&1\cr\cr 0&1&1&1\cr\cr 1&1&1&2\end{pmatrix}

D'après la calculatrice, on obtient :

A ^2=\begin{pmatrix} 3& 1&0&1 \cr\cr 1&2 &1&1\cr\cr 0&1&1&1\cr\cr 1&1&1&2\end{pmatrix}

Par déduction, quel est le nombre de chemins de longueur 2 allant de A vers D ?

Il existe deux chemins de longueur 2 reliant A à D.

Il existe un chemin de longueur 2 reliant A à D.

Il existe trois chemins de longueur 2 reliant A à D.

Il existe aucun chemin de longueur 2 reliant A à 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 2 allant de A vers D, il sera donc égal à a_{1;4}.

On remarque ici que a_{1;4} = 1, cela signifie qu'il existe une chaîne de longueur 2 partant du point A et aboutissant au point D.

Il existe un chemin de longueur 2 reliant A à D.