On considère le graphe non orienté $G$ de sommets $A$, $B$, $C$, $D$, $E$, dont les arêtes sont $$\{A,B\},\ \{A,C\},\ \{B,C\},\ \{B,D\},\ \{C,D\},\ \{D,E\}.$$
- Donner l'ordre de $G$ et le degré de chaque sommet. Vérifier la propriété de la somme des degrés.
- Le graphe $G$ est-il connexe ? complet ? Combien d'arêtes faudrait-il ajouter pour le rendre complet ?
- Écrire la matrice d'adjacence $M$ de $G$, les sommets étant rangés dans l'ordre alphabétique.
- Sans calculer $M^2$ en entier, déterminer son coefficient situé ligne $1$, colonne $4$, puis son coefficient ligne $5$, colonne $5$. Interpréter ces nombres et écrire les chaînes correspondantes.
Le degré d'un sommet est le nombre d'arêtes dont il est une extrémité.
Un graphe complet d'ordre $n$ a $\frac{n(n-1)}{2}$ arêtes.
Le coefficient $(i,j)$ de $M^2$ s'obtient avec la ligne $i$ et la colonne $j$ de $M$ ; il compte les chaînes de longueur $2$ de $i$ à $j$.
- $G$ a $5$ sommets : il est d'ordre $5$.
| Sommet | $A$ | $B$ | $C$ | $D$ | $E$ |
|---|---|---|---|---|---|
| Degré | 2 | 3 | 3 | 3 | 1 |
La somme des degrés vaut $2+3+3+3+1=12=2\times 6$, et $G$ a bien $6$ arêtes.
-
La chaîne $A-B-C-D-E$ passe par tous les sommets ; deux sommets quelconques sont donc reliés par une portion de cette chaîne : $G$ est connexe. $G$ n'est pas complet : par exemple $A$ et $E$ ne sont pas adjacents. Un graphe complet d'ordre $5$ possède $\frac{5\times 4}{2}=10$ arêtes ; il faudrait en ajouter $10-6=4$ (ce sont $\{A,D\}$, $\{A,E\}$, $\{B,E\}$, $\{C,E\}$).
-
$$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}$$ Elle est symétrique, de diagonale nulle, et la somme de chaque ligne est le degré du sommet.
-
Coefficient $(1,4)$ de $M^2$ : ligne $1$ de $M$, $(0,1,1,0,0)$, et colonne $4$ de $M$, $(0,1,1,0,1)$ : $$0\times 0+1\times 1+1\times 1+0\times 0+0\times 1=2.$$ Il existe $2$ chaînes de longueur $2$ de $A$ à $D$ : $A-B-D$ et $A-C-D$.
Coefficient $(5,5)$ de $M^2$ : ligne $5$, $(0,0,0,1,0)$, et colonne $5$, $(0,0,0,1,0)$ : la somme vaut $1$. Il existe une seule chaîne fermée de longueur $2$ partant de $E$ : $E-D-E$. On retrouve le degré de $E$.
Ordre 5 ; degrés 2, 3, 3, 3, 1 ; connexe, non complet, 4 arêtes à ajouter ; coefficients de $M^2$ : $(1,4)=2$ et $(5,5)=1$