Exercice 16

1. Le graphe a $5$ sommets, il est donc d'ordre $5$. Les degrés sont :

La somme des degrés vaut $12$, deux fois le nombre d'arêtes, qui est $6$. Le graphe n'est pas complet, car $A$ et $E$ ne sont pas adjacents par exemple. Il est connexe : tout sommet est relié à $D$ par une chaîne ($A$--$B$--$D$, $B$--$D$, $C$--$D$, $E$--$D$), donc deux sommets quelconques sont reliés en passant par $D$.

2. $$\boxed{M=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}}$$

3. La calculatrice donne : $$M^{2}=\begin{pmatrix} \textcolor{#9e0018}{2} & 1 & 1 & 2 & 0 \\ 1 & \textcolor{#9e0018}{3} & 2 & 1 & 1 \\ 1 & 2 & \textcolor{#9e0018}{3} & 1 & 1 \\ 2 & 1 & 1 & \textcolor{#9e0018}{3} & 0 \\ 0 & 1 & 1 & 0 & \textcolor{#9e0018}{1} \end{pmatrix}$$ La diagonale de $M^{2}$ est formée des degrés des sommets. D'après la Proposition 2, le coefficient $(i\,;i)$ de $M^{2}$ compte les chaînes de longueur $2$ partant de $i$ et revenant en $i$. Une telle chaîne est un aller-retour $i$--$k$--$i$ le long d'une arête, et il y en a autant que d'arêtes issues de $i$, c'est-à-dire le degré de $i$. Ce raisonnement suppose le graphe sans boucle et sans arête multiple.

4. Il faut calculer $M^{3}$ et lire le coefficient en ligne $A$ et colonne $E$, c'est-à-dire en ligne $1$, colonne $5$ : $$M^{3}=\begin{pmatrix} 2 & 5 & 5 & 2 & \textcolor{#9e0018}{2} \\ 5 & 4 & 5 & 6 & 1 \\ 5 & 5 & 4 & 6 & 1 \\ 2 & 6 & 6 & 2 & 3 \\ 2 & 1 & 1 & 3 & 0 \end{pmatrix} \qquad \boxed{\text{il y a } 2 \text{ chaînes de longueur } 3 \text{ reliant } A \text{ à } E}$$ Ce sont $A$--$B$--$D$--$E$ et $A$--$C$--$D$--$E$. C'est cohérent : $E$ n'est relié qu'à $D$, et une chaîne de longueur $2$ de $A$ à $D$ passe nécessairement par $B$ ou par $C$.