Graphes et matrice d'adjacence

a) On place un 1 dès que deux sommets sont reliés, 0 sinon.
Ligne A : relié à B et C, donc $(0 \ 1 \ 1 \ 0)$.
Ligne B : relié à A et C, donc $(1 \ 0 \ 1 \ 0)$.
Ligne C : relié à A, B et D, donc $(1 \ 1 \ 0 \ 1)$.
Ligne D : relié à C seulement, donc $(0 \ 0 \ 1 \ 0)$.
La matrice est symétrique, comme toujours pour un graphe non orienté.
Calculons $M^{2}$, dont le coefficient $(i ; j)$ est le produit de la ligne $i$ par la colonne $j$.
Ligne A de $M^{2}$ : $A \cdot A = 0 + 1 + 1 + 0 = 2$.
$A \cdot B = 0 + 0 + 1 + 0 = 1$. $A \cdot C = 0 + 1 + 0 + 0 = 1$. $A \cdot D = 0 + 0 + 1 + 0 = 1$.
Ligne A : $(2 \ 1 \ 1 \ 1)$.
Ligne B : $B \cdot A = 1$, $B \cdot B = 2$, $B \cdot C = 1$, $B \cdot D = 1$, soit $(1 \ 2 \ 1 \ 1)$.
Ligne C : $C \cdot A = 1$, $C \cdot B = 1$, $C \cdot C = 3$, $C \cdot D = 0$, soit $(1 \ 1 \ 3 \ 0)$.
Ligne D : $D \cdot A = 1$, $D \cdot B = 1$, $D \cdot C = 0$, $D \cdot D = 1$, soit $(1 \ 1 \ 0 \ 1)$.

b) Le coefficient $(i ; j)$ de $M^{2}$ donne le nombre de chaînes de longueur 2 de $i$ à $j$.
De A à D : le coefficient vaut 1.
Il s'agit du chemin $A - C - D$, le seul possible en deux arêtes.
De B à B : le coefficient vaut 2.
Il s'agit des allers-retours $B - A - B$ et $B - C - B$.
Ce nombre est d'ailleurs le degré de B, ce qui est vrai pour tout sommet.
On le vérifie sur C : le coefficient vaut 3, et C est bien de degré 3 ✓.
Et sur D : le coefficient $(D ; D)$ vaut 1, et D n'a qu'un seul voisin ✓.
La somme des degrés vaut $2 + 2 + 3 + 1 = 8$, soit deux fois le nombre d'arêtes.
Le graphe a donc bien 4 arêtes, ce que confirme l'énoncé ✓.
On peut aussi lire $M^{2}$ ligne par ligne : la somme d'une ligne donne le nombre total
de chaînes de longueur 2 issues du sommet correspondant.
Pour A : $2 + 1 + 1 + 1 = 5$ chaînes de longueur 2 au départ de A.
Cela correspond bien à 2 voisins, chacun offrant ensuite son propre degré de choix ($2 + 3 = 5$) ✓.

a) Chaque sommet est relié aux trois autres, et jamais à lui-même.
Tous les coefficients hors diagonale valent 1, la diagonale est nulle.
Calculons un coefficient diagonal de $M^{2}$, par exemple $(1 ; 1)$.
On multiplie la ligne 1, $(0 \ 1 \ 1 \ 1)$, par la colonne 1, $(0 \ 1 \ 1 \ 1)$.
$0 \times 0 + 1 \times 1 + 1 \times 1 + 1 \times 1 = 3$.
Calculons maintenant un coefficient hors diagonale, par exemple $(1 ; 2)$.
Ligne 1 : $(0 \ 1 \ 1 \ 1)$ ; colonne 2 : $(1 \ 0 \ 1 \ 1)$.
$0 \times 1 + 1 \times 0 + 1 \times 1 + 1 \times 1 = 2$.
Par symétrie du graphe, tous les coefficients diagonaux valent 3.
Et tous les coefficients hors diagonale valent 2.
$M^{2}$ a donc des 3 sur la diagonale et des 2 partout ailleurs.

b) Entre deux sommets distincts, il y a 2 chaînes de longueur 2.
Pour aller de 1 à 2, il faut passer par un sommet intermédiaire.
Ce sommet ne peut être ni 1 ni 2 : il reste 3 et 4, soit 2 possibilités ✓.
D'un sommet à lui-même, il y a 3 chaînes de longueur 2.
Pour revenir en 1, on va vers un voisin puis on revient.
Il y a 3 voisins possibles, donc 3 chaînes ✓.
On retrouve bien que ce nombre est le degré du sommet.
Dans un graphe complet à $n$ sommets, ce degré vaut toujours $n - 1$.
De même, entre deux sommets distincts, il y a toujours $n - 2$ chaînes de longueur 2.
On peut généraliser : $M = J - I$, où $J$ est la matrice remplie de 1.
Comme $J^{2} = nJ$, on obtient $M^{2} = J^{2} - 2J + I = (n-2)J + I$.
Pour $n = 4$ : les coefficients hors diagonale valent 2 et la diagonale $2 + 1 = 3$ ✓.
La somme d'une ligne de $M^{2}$ vaut $3 + 2 + 2 + 2 = 9 = 3^{2}$.
C'est logique : au départ d'un sommet, on a 3 choix puis encore 3, soit 9 chaînes.
Le graphe complet est le cas où le nombre de chemins croît le plus vite avec la longueur.