Graphes : vocabulaire, exercices corrigés de Terminale expertes

Le graphe a cinq sommets $A$, $B$, $C$, $D$, $E$ : son ordre est $5$.

On repasse chaque arête et on note les voisins : $A$ : $B$, $C$ ; $B$ : $A$, $C$ ; $C$ : $A$, $B$, $D$, $E$ ; $D$ : $C$, $E$ ; $E$ : $C$, $D$.

Le degré d'un sommet est son nombre de connexions ³, donc le nombre de voisins ici (pas d'arête multiple) : $d(A)=2$, $d(B)=2$, $d(C)=4$, $d(D)=2$, $d(E)=2$.

Contrôle : la somme des degrés est $2+2+4+2+2=12$, soit le double des $6$ arêtes. Le compte est cohérent.

Additionnons les degrés : $3+3+2+2+2+1+1=14$.

Chaque arête a deux extrémités, elle est donc comptée exactement deux fois dans cette somme (une fois pour chaque extrémité).

Le nombre d'arêtes vaut donc $\frac{14}{2}=7$.

Chaque sommet est adjacent aux $6-1=5$ autres : son degré est $5$.

Les $6$ sommets ont tous le degré $5$ : la somme des degrés est $6\times 5=30$.

Chaque arête étant comptée deux fois, le nombre d'arêtes est $\frac{30}{2}=15$.

Vérifions chaque couple consécutif de $A - B - C - D - E$ : $AB$, $BC$, $CD$, $DE$ sont des arêtes. C'est donc une chaîne.

Sa longueur est son nombre d'arêtes, soit $4$ (et non $5$, nombre de sommets).

Dans $A - B - D$, le couple $B\,D$ n'est pas une arête (voisins de $B$ : $A$ et $C$). Ce n'est pas une chaîne.

$A$ et $E$ ne sont pas adjacents (voisins de $A$ : $B$, $C$), donc aucune chaîne de longueur $1$ ne convient.

La suite $A - C - E$ est une chaîne : $AC$ et $CE$ sont des arêtes. Sa longueur est $2$, c'est donc la longueur minimale.

Ligne de $A$ : voisins $B$, $C$, donc $(0\;1\;1\;0\;0)$. Ligne de $B$ : $(1\;0\;1\;0\;0)$. Ligne de $C$ : $(1\;1\;0\;1\;1)$. Ligne de $D$ : $(0\;0\;1\;0\;1)$. Ligne de $E$ : $(0\;0\;1\;1\;0)$.

La matrice est symétrique : si $i$ est adjacent à $j$, alors $j$ est adjacent à $i$, car une arête n'a pas de sens de parcours.

La somme d'une ligne donne le degré du sommet : $2$, $2$, $4$, $2$, $2$. La somme de tous les coefficients est $2+2+4+2+2=12$.

Chaque arête apparaît deux fois dans la matrice (à la position $(i,j)$ et à la position $(j,i)$) : $12=2\times 6$, ce qui correspond bien aux $6$ arêtes.

Si les $5$ sommets ont tous le degré $3$, la somme des degrés vaut $5\times 3=15$.

Cette somme doit être le double du nombre d'arêtes, donc un nombre pair.

Or $15$ est impair : le nombre d'arêtes vaudrait $7{,}5$, ce qui est impossible.

Aucun graphe de ce type n'existe : Léa a tort.

Dans un graphe complet d'ordre $n$, chaque sommet est de degré $n-1$. La somme des degrés est $n(n-1)$ et le nombre d'arêtes est $\frac{n(n-1)}{2}$.

On résout $\frac{n(n-1)}{2}=45$, soit $n^2-n-90=0$.

Le discriminant est $\Delta=1+360=361=19^2$.

Les solutions sont $n=\frac{1-19}{2}=-9$ et $n=\frac{1+19}{2}=10$. L'ordre est un entier positif : $n=10$.

Vérification : $\frac{10\times 9}{2}=45$.

Ligne $1$ : arcs vers $2$ et $3$, donc $(0\;1\;1\;0)$. Ligne $2$ : arc vers $3$, donc $(0\;0\;1\;0)$. Ligne $3$ : arcs vers $1$ et $4$, donc $(1\;0\;0\;1)$. Ligne $4$ : arc vers $2$, donc $(0\;1\;0\;0)$.

Deux arcs partent du sommet $3$ (somme de la ligne $3$ : $1+0+0+1=2$).

Dans la colonne $2$, on lit $1+0+0+1=2$ : deux arcs arrivent au sommet $2$ ($1\to 2$ et $4\to 2$).

La matrice n'est pas symétrique : l'arc $1\to 2$ existe, mais pas l'arc $2\to 1$ ; le coefficient $(1,2)$ vaut $1$ et le coefficient $(2,1)$ vaut $0$.