Savoir utiliser la matrice d'adjacence d'un graphe - Exercice 1

$$M=\left(\begin{array}{ccccc} {0} & {1} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \\ {1} & {0} & {0} & {1} & {0} \\ {0} & {1} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \end{array}\right)$$

D'après la calculatrice, on obtient :
$$M^{2}=\left(\begin{array}{ccccc} {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {2} & {0} & {2} \\ {0} & {2} & {2} & {0} & {2} \\ {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {2} & {0} & {2} \end{array}\right)$$

Pour déterminer le nombre de chemins de longueur $$2$$ reliant le sommet $$B$$ au sommet sommet $$C$$, on doit calculer $$M^{2}$$ . D'après la question $$2$$, nous connaissons $$M^{2}$$ .
Nous allons prendre la valeur de l'intersection entre la deuxième ligne ( en référence au sommet $$B$$ ) et de la troisième colonne ( en référence au sommet $$C$$ )
Nous mettons $$\red{\text{en rouge}}$$ cette valeur dans la matrice $$M^{2}$$
$$M^{2}=\left(\begin{array}{ccccc} {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {{\color{red}{2}}} & {0} & {2} \\ {0} & {2} & {2} & {0} & {2} \\ {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {2} & {0} & {2} \end{array}\right)$$
Il y a donc $${\color{red}{2}}$$ chemins de longueur $$2$$ reliant le sommet $$B$$ au sommet $$C$$ .

D'après la calculatrice, on obtient :
$$M^{3}=\left(\begin{array}{ccccc} {0} & {6} & {6} & {0} & {6} \\ {6} & {0} & {0} & {6} & {0} \\ {6} & {0} & {0} & {6} & {0} \\ {0} & {6} & {6} & {0} & {6} \\ {6} & {0} & {0} & {6} & {0} \end{array}\right)$$

Pour déterminer le nombre de chemins de longueur $$3$$ reliant le sommet $$A$$ au sommet sommet $$E$$, on doit calculer $$M^{3}$$ . D'après la question $$4$$, nous connaissons $$M^{3}$$ .
Nous allons prendre la valeur de l'intersection entre la première ligne ( en référence au sommet $$A$$ ) et de la cinquième colonne ( en référence au sommet $$E$$ )
Nous mettons $$\red{\text{en rouge}}$$ cette valeur dans la matrice $$M^{3}$$
$$M^{3}=\left(\begin{array}{ccccc} {0} & {6} & {6} & {0} & {{\color{red}{6}}} \\ {6} & {0} & {0} & {6} & {0} \\ {6} & {0} & {0} & {6} & {0} \\ {0} & {6} & {6} & {0} & {6} \\ {6} & {0} & {0} & {6} & {0} \end{array}\right)$$
Il y a donc $${\color{red}{6}}$$ chemins de longueur $$3$$ reliant le sommet $$A$$ au sommet $$E$$ .