Graphes et matrice d'adjacence

a) Le coefficient $(i ; i)$ de $M^{2}$ compte les chaînes de longueur 2 de $i$ vers $i$.
Une telle chaîne consiste à aller vers un voisin, puis à revenir.
Il y a donc exactement autant de chaînes que de voisins.
Ces coefficients sont donc les degrés des quatre sommets.
Les degrés valent respectivement 2, 3, 3 et 2.

b) La somme des degrés vaut $2 + 3 + 3 + 2 = 10$.
Or chaque arête est comptée deux fois dans cette somme, une par extrémité.
C'est le lemme des poignées de main.
Le nombre d'arêtes vaut donc $\frac{10}{2} = 5$.
On peut vérifier qu'un tel graphe existe : par exemple le carré $A-B-C-D-A$ plus la diagonale $B-D$.
Les degrés sont alors 2 pour A, 3 pour B, 2 pour C et 3 pour D.
En réordonnant les sommets, on retrouve bien la diagonale annoncée.
On peut vérifier autrement : un graphe à 4 sommets a au plus $\frac{4 \times 3}{2} = 6$ arêtes.
Avec 5 arêtes, il ne manque donc qu'une seule arête au graphe complet.
Dans le graphe complet, tous les degrés valent 3.
Retirer une arête abaisse de 1 le degré de ses deux extrémités : on obtient bien $(2 ; 3 ; 3 ; 2)$.
La diagonale de $M^{2}$ ne suffit pourtant pas à déterminer le graphe entièrement.
Elle donne les degrés, mais pas la façon dont les arêtes sont réparties.
Il faudrait les coefficients hors diagonale pour reconstituer $M$.

a) Ligne A : $(0 \ 1 \ 1)$. Ligne B : $(1 \ 0 \ 1)$. Ligne C : $(1 \ 1 \ 0)$.
Calculons $M^{2}$.
$(A ; A) = 0 + 1 + 1 = 2$.
$(A ; B)$ : ligne A fois colonne B, soit $(0 \ 1 \ 1) \cdot (1 \ 0 \ 1) = 1$.
$(A ; C) = (0 \ 1 \ 1) \cdot (1 \ 1 \ 0) = 1$.
Par symétrie, $M^{2}$ a des 2 sur la diagonale et des 1 partout ailleurs.
Calculons $M^{3} = M^{2} \times M$.
Ligne A de $M^{2}$ : $(2 \ 1 \ 1)$.
$(A ; A)$ de $M^{3}$ : $(2 \ 1 \ 1) \cdot (0 \ 1 \ 1) = 0 + 1 + 1 = 2$.
$(A ; B)$ : $(2 \ 1 \ 1) \cdot (1 \ 0 \ 1) = 2 + 0 + 1 = 3$.
$(A ; C)$ : $(2 \ 1 \ 1) \cdot (1 \ 1 \ 0) = 2 + 1 + 0 = 3$.
$M^{3}$ a donc des 2 sur la diagonale et des 3 ailleurs.

b) De A à A en 3 arêtes : le coefficient vaut 2.
Ce sont les deux parcours du triangle : $A - B - C - A$ et $A - C - B - A$.
Ce sont les deux sens de rotation du même cycle.
Contrairement au carré, le triangle admet des chaînes fermées de longueur impaire.
Ce graphe n'est donc pas biparti, ce que confirment les coefficients non nuls partout dans $M^{3}$.
On peut aussi vérifier la somme d'une ligne de $M^{3}$ : $2 + 3 + 3 = 8 = 2^{3}$.
C'est logique : à chaque pas, on a 2 choix, et il y a 3 pas.
Les degrés valent tous 2, ce que confirme la diagonale de $M^{2}$.
La somme des degrés vaut 6, soit 3 arêtes.
On remarque enfin la relation $M^{2} = M + 2I$, caractéristique du triangle.
Elle permet de calculer toutes les puissances sans nouveau produit matriciel.
Par exemple $M^{3} = M \times M^{2} = M^{2} + 2M = 3M + 2I$, ce qui redonne bien les coefficients trouvés.