Quiz — Graphes

Question 1 : Combien d'arêtes possède le graphe complet $K_6$ ?

• $30$
• ✓ $15$
• $12$
• $6$

Explication : D'après le **Théorème 2 (arêtes du graphe complet)**, $K_n$ possède $\dfrac{n(n-1)}{2}$ arêtes : pour $n = 6$, $\dfrac{6 \times 5}{2} = 15$ arêtes, option B. La réponse $30$ compte deux fois chaque arête : c'est la somme des degrés, conformément au **Théorème 1 (lemme des poignées de mains)**.

Question 2 : Un graphe non orienté possède $7$ arêtes. Que vaut la somme des degrés de ses sommets ?

• $7$
• $21$
• ✓ $14$
• On ne peut pas savoir sans connaître le nombre de sommets

Explication : **Méthode 1 — exploiter le lemme des poignées de mains** : d'après le **Théorème 1 (lemme des poignées de mains)**, la somme des degrés vaut le double du nombre d'arêtes, soit $2 \times 7 = 14$ : option C. Chaque arête apporte $1$ au degré de chacune de ses deux extrémités ; le nombre de sommets n'intervient pas.

Question 3 : Existe-t-il un graphe non orienté dont les cinq sommets ont pour degrés $3,\ 3,\ 2,\ 2,\ 1$ ?

• Oui, il a $5$ arêtes
• Oui, il a $6$ arêtes
• Non, car un sommet de degré $1$ est impossible avec $5$ sommets
• ✓ Non, car la somme des degrés serait impaire

Explication : **Méthode 1 — exploiter le lemme des poignées de mains** : la somme des degrés vaut $3+3+2+2+1 = 11$, nombre impair. Or, d'après le **Théorème 1 (lemme des poignées de mains)**, elle doit être égale au double du nombre d'arêtes, donc paire : un tel graphe n'existe pas, option D. Autre formulation : le nombre de sommets de degré impair est toujours pair, ici il vaudrait $3$.

Question 4 : On considère le graphe ci-dessous, sommets rangés dans l'ordre $A, B, C, D$. Quelle est sa matrice d'adjacence ?

• ✓ $\begin{pmatrix} 0&1&1&1 \\ 1&0&0&0 \\ 1&0&0&1 \\ 1&0&1&0 \end{pmatrix}$
• $\begin{pmatrix} 0&1&1&1 \\ 1&0&1&1 \\ 1&1&0&1 \\ 1&1&1&0 \end{pmatrix}$
• $\begin{pmatrix} 3&1&1&1 \\ 1&1&0&0 \\ 1&0&2&1 \\ 1&0&1&2 \end{pmatrix}$
• $\begin{pmatrix} 0&1&1&1 \\ 0&0&0&0 \\ 0&0&0&1 \\ 0&0&0&0 \end{pmatrix}$

Explication : **Méthode 2 — écrire la matrice d'adjacence** : les arêtes sont $AB$, $AC$, $AD$ et $CD$. D'après la **Définition 5 — matrice d'adjacence**, on place un $1$ ligne $i$ colonne $j$ lorsque $i$ et $j$ sont adjacents, et un $0$ sinon (diagonale nulle : pas de boucle). Le graphe étant non orienté, la matrice est symétrique : option A. La deuxième matrice est celle de $K_4$, la quatrième n'est pas symétrique.

Question 5 : Soit $A$ la matrice d'adjacence d'un graphe simple non orienté. Que représente le coefficient diagonal $(A^2)_{ii}$ ?

• Le nombre de triangles contenant le sommet $i$
• ✓ Le degré du sommet $i$
• Toujours $0$, car il n'y a pas de boucle
• Le carré du degré du sommet $i$

Explication : D'après le **Théorème 3 (nombre de chemins de longueur $n$)**, $(A^2)_{ii}$ compte les chemins de longueur $2$ de $i$ à $i$, c'est-à-dire les aller-retours $i \to j \to i$ sur une arête $ij$. Il y en a exactement un par arête incidente à $i$, donc $(A^2)_{ii} = d(i)$ : option B. Calcul : $(A^2)_{ii} = \sum_j a_{ij}a_{ji} = \sum_j a_{ij}^2 = \sum_j a_{ij}$ car les coefficients valent $0$ ou $1$.

Question 6 : Dans le graphe d'arêtes $AB$, $AC$, $AD$, $CD$, combien y a-t-il de chemins de longueur $2$ allant de $B$ à $C$ ?

• $0$
• $2$
• $3$
• ✓ $1$

Explication : **Méthode 3 — compter les chemins de longueur $n$** : un chemin de longueur $2$ de $B$ à $C$ passe par un sommet intermédiaire adjacent à la fois à $B$ et à $C$. Le seul voisin de $B$ est $A$, qui est bien adjacent à $C$ : unique chemin $B \to A \to C$, option D. C'est le coefficient $(A^2)_{BC} = \sum_k a_{Bk}a_{kC} = a_{BA}a_{AC} = 1$ du **Théorème 3 (nombre de chemins de longueur $n$)**.

Question 7 : Un graphe connexe a pour degrés $3,\ 1,\ 2,\ 2$ (sommets $A, B, C, D$). Admet-il une chaîne eulérienne ?

• ✓ Oui, elle part nécessairement de $A$ ou de $B$
• Oui, elle peut partir de n'importe quel sommet
• Non, car il y a des sommets de degré impair
• Non, car il faut exactement un sommet de degré impair

Explication : **Méthode 4 — décider de l'existence d'une chaîne eulérienne** : le graphe est connexe et possède exactement deux sommets de degré impair ($A$ de degré $3$ et $B$ de degré $1$). D'après le **Théorème 4 (théorème d'Euler)**, il admet une chaîne eulérienne dont les extrémités sont obligatoirement ces deux sommets : option A. Par exemple $B \to A \to C \to D \to A$. Un cycle eulérien (départ quelconque) exigerait que tous les degrés soient pairs.

Question 8 : Soit $M$ la matrice d'adjacence d'un graphe orienté. Que signifie $m_{ij} = 1$ ?

• Les sommets $i$ et $j$ sont reliés, dans un sens ou dans l'autre
• Il existe un arc de $j$ vers $i$
• ✓ Il existe un arc de $i$ vers $j$
• Le sommet $i$ est de degré $1$

Explication : D'après la **Définition 5 — matrice d'adjacence**, la ligne correspond au sommet de départ et la colonne au sommet d'arrivée : $m_{ij} = 1$ signifie qu'il y a un arc $i \to j$, option C. Dans un graphe orienté (**Définition 4**), on peut avoir $m_{ij} = 1$ et $m_{ji} = 0$ : la matrice n'est pas symétrique en général, contrairement au cas non orienté.

Question 9 : Un graphe non orienté a pour sommets $A, B, C, D$ et pour seules arêtes $AB$ et $CD$. Lequel des énoncés est vrai ?

• ✓ Il n'est pas connexe : il a deux composantes connexes
• Il est connexe car chaque sommet est de degré $1$
• Il est connexe car il possède autant d'arêtes que de paires de sommets reliés
• Il n'est pas connexe car il possède un cycle

Explication : D'après la **Définition 3 — chaîne, cycle, connexité**, un graphe est connexe si deux sommets quelconques sont reliés par une chaîne. Or aucune chaîne ne relie $A$ à $C$ : le graphe n'est pas connexe, option A. Ses composantes connexes sont $\{A, B\}$ et $\{C, D\}$, et sa matrice d'adjacence (**Définition 5**) est diagonale par blocs : $\begin{pmatrix} 0&1&0&0 \\ 1&0&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \end{pmatrix}$.

Question 10 : Question type bac. Un graphe orienté a pour sommets $A, B, C$ et pour arcs $A \to B$, $B \to C$, $C \to A$ et $A \to C$. Sa matrice d'adjacence est $M = \begin{pmatrix} 0&1&1 \\ 0&0&1 \\ 1&0&0 \end{pmatrix}$. Combien y a-t-il de chemins de longueur $3$ allant de $A$ à $A$ ?

• $0$
• ✓ $1$
• $2$
• $3$

Explication : **Méthode 3 — compter les chemins de longueur $n$** : on calcule $M^2 = \begin{pmatrix} 1&0&1 \\ 1&0&0 \\ 0&1&1 \end{pmatrix}$ puis $M^3 = M^2 M = \begin{pmatrix} 1&1&1 \\ 0&1&1 \\ 1&0&1 \end{pmatrix}$. D'après le **Théorème 3 (nombre de chemins de longueur $n$)**, $(M^3)_{AA} = 1$ : l'unique chemin est $A \to B \to C \to A$, option B. Vérification directe : $A \to C \to A$ revient en deux étapes seulement, puis il faut repartir, on n'est plus en $A$ au bout de $3$ étapes.