Devoir type n°1 (1 h) - Exercice 2

Le coefficient de la ligne $$i$$ et de la colonne $$j$$ vaut $$1$$ si les $$i$$-ième et $$j$$-ième sommets sont adjacents, et $$0$$ sinon.
Finalement :

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

Nous allons prendre la valeur de l'intersection entre la première ligne (en référence au sommet $$A$$) et 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} & {1} & {{\color{red}{2}}} & {1} & {1} \\ {1} & {2} & {1} & {2} & {0} \\ {2} & {1} & {3} & {1} & {1} \\ {1} & {2} & {1} & {3} & {0} \\ {1} & {0} & {1} & {0} & {1} \end{array}\right)$$
Il y a donc $${\color{red}{2}}$$ chemins de longueur $$2$$ reliant le sommet $$A$$ au sommet $$C$$ .
Ce sont :

Nous allons prendre la valeur de l'intersection entre la quatrième ligne (en référence au sommet $$D$$) et 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} {4} & {5} & {5} & {6} & {1} \\ {5} & {2} & {5} & {2} & {2} \\ {5} & {5} & {4} & {6} & {1} \\ {6} & {2} & {6} & {2} & {{\color{red}{3}}} \\ {1} & {2} & {1} & {3} & {0} \end{array}\right)$$
Il y a donc $${\color{red}{3}}$$ chemins de longueur $$3$$ allant du sommet $$D$$ au sommet $$E$$ .
Le seul sommet adjacent à $$E$$ est $$D$$ : un tel chemin s'écrit $$D-x-D-E$$ , où $$x$$ est un sommet adjacent à $$D$$ ($$A$$ , $$C$$ ou $$E$$). Ce sont :
Un chemin peut passer plusieurs fois par le même sommet ou la même arête.