[enonce]
Pour chaque affirmation suivante sur le vocabulaire et les représentations des graphes, indiquer si elle est Vraie ou Fausse.
[/enonce]

[etape]
Affirmation : L'ordre d'un graphe est égal au nombre d'arêtes qu'il contient.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Bonne réponse !
L'ordre d'un graphe est par définition son nombre de sommets, pas son nombre d'arêtes. Un graphe à $4$ sommets et $10$ arêtes est d'ordre $4$, pas $10$.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Attention à ne pas confondre les deux quantités fondamentales d'un graphe. L'ordre compte les sommets ; le nombre d'arêtes est une autre grandeur, souvent notée séparément.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. L'ordre d'un graphe est son nombre de sommets, pas son nombre d'arêtes.
[/solution]
[/etape]

[etape]
Affirmation : Dans un graphe non orienté, une boucle sur un sommet ajoute $2$ au degré de ce sommet.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Exactement !
La convention pour les graphes non orientés est que la boucle « part » du sommet et y « revient » : elle contribue donc deux fois au degré. Cela rend cohérente la propriété « la somme des degrés vaut deux fois le nombre d'arêtes ».[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Le piège est de penser qu'une boucle est une seule arête comptée pour $1$. Pour préserver la formule de la somme des degrés, on convient qu'une boucle pèse $2$ dans le degré du sommet correspondant.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. Par convention, dans un graphe non orienté, une boucle compte deux fois dans le degré du sommet sur lequel elle est posée.
[/solution]
[/etape]

[etape]
Affirmation : Tout graphe complet est connexe.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Bravo !
Dans un graphe complet, tous les sommets sont deux à deux adjacents (reliés par une arête directe). Pour relier deux sommets, il suffit donc de l'arête qui les joint : la condition de connexité est satisfaite trivialement.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Rappel : un graphe est complet quand tous les sommets sont deux à deux adjacents. Or l'adjacence directe implique la connexité, puisqu'une seule arête suffit alors comme « chaîne » entre deux sommets.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. Dans un graphe complet, deux sommets quelconques sont reliés par une arête, donc directement par une chaîne de longueur $1$.
[/solution]
[/etape]

[etape]
Affirmation : Si deux sommets d'un graphe ont le même degré, alors ils sont nécessairement adjacents.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]Tu as raison !
L'adjacence et l'égalité des degrés sont deux propriétés indépendantes. Par exemple, dans un graphe formé de deux paires d'arêtes disjointes, les quatre sommets sont tous de degré $1$ mais seuls les sommets reliés sont adjacents.[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
L'adjacence dépend de l'existence d'une arête entre les deux sommets. Le degré ne mesure que le nombre total d'arêtes qui touchent un sommet, sans dire avec qui il est connecté.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. Deux sommets de même degré ne sont pas nécessairement adjacents : un contre-exemple suffit, par exemple deux arêtes disjointes donnent quatre sommets de degré $1$ mais non tous adjacents.
[/solution]
[/etape]

[etape]
Affirmation : Dans un graphe non orienté, la somme des degrés de tous les sommets est égale au nombre d'arêtes.

[qcm]
[option]Vrai[/option]
[option correct="true"]Faux[/option]
[reponse statut="correct"]C'est bien ça !
Chaque arête est comptée deux fois dans la somme des degrés (une fois pour chacune de ses extrémités). On a donc « somme des degrés = $2 \times$ nombre d'arêtes », pas « = nombre d'arêtes ».[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est fausse.
Petit piège classique. Visualiser une seule arête $AB$ : elle contribue $1$ au degré de $A$ et $1$ au degré de $B$, donc $2$ au total dans la somme des degrés, alors qu'elle ne représente qu'une seule arête.[/reponse]
[/qcm]

[solution]
Cette affirmation est fausse. La somme des degrés vaut $2 \times$ le nombre d'arêtes, car chaque arête est comptée à ses deux extrémités.
[/solution]
[/etape]

[etape]
Affirmation : Un graphe peut être connexe sans être complet.

[qcm]
[option correct="true"]Vrai[/option]
[option]Faux[/option]
[reponse statut="correct"]Parfait !
La connexité demande seulement qu'on puisse relier deux sommets quelconques par une chaîne, pas nécessairement par une arête directe. Un chemin simple à $4$ sommets $A-B-C-D$ est connexe (un seul morceau), mais pas complet ($A$ et $D$ ne sont pas reliés directement).[/reponse]
[reponse statut="incorrect"]Non, cette affirmation est vraie.
Confusion classique entre les deux notions. Tout graphe complet est connexe, mais l'inverse est faux : la connexité est une condition nettement plus faible que la complétude.[/reponse]
[/qcm]

[solution]
Cette affirmation est vraie. Par exemple, un chemin $A-B-C-D$ est connexe (toujours un seul morceau) mais pas complet (les sommets non voisins ne sont pas reliés directement).
[/solution]
[/etape]

[enonce]
Ce QCM porte sur le vocabulaire des graphes : ordre, degré, sommets adjacents, connexité, chaîne et cycle. Pour chaque question, choisissez la bonne réponse parmi les quatre propositions.
[/enonce]

[etape]
Que désigne l'ordre d'un graphe ?
[qcm]
[option]Le nombre d'arêtes du graphe.[/option]
[option correct="true"]Le nombre de sommets du graphe.[/option]
[option]Le degré le plus grand parmi tous les sommets.[/option]
[option]La longueur de la plus longue chaîne du graphe.[/option]
[reponse statut="correct"]Exactement !
L'ordre d'un graphe est le nombre de ses sommets. Par exemple, un graphe qui possède 5 sommets est dit d'ordre $5$, peu importe le nombre d'arêtes.[/reponse]
[reponse motif="Le nombre d'arêtes du graphe."]Non.
Confusion fréquente entre deux notions distinctes : ce qui est compté ici est ce qui relie les sommets, pas les sommets eux-mêmes.[/reponse]
[reponse motif="Le degré le plus grand parmi tous les sommets."]Non.
Cette quantité s'appelle le degré maximal (souvent noté $d_{\max}$). Elle sert pour majorer le nombre chromatique, mais ce n'est pas l'ordre du graphe.[/reponse]
[reponse motif="La longueur de la plus longue chaîne du graphe."]Non.
La longueur d'une chaîne mesure le nombre d'arêtes parcourues. Cette grandeur n'a pas de nom usuel dans le programme et ne correspond pas à l'ordre.[/reponse]
[reponse statut="incorrect"]Non.
Par définition, l'ordre d'un graphe est le nombre de ses sommets.[/reponse]
[/qcm]
[/etape]

[etape]
Soit un graphe non orienté dont un sommet $A$ porte une boucle et est relié par une arête à $3$ autres sommets. Quel est le degré de $A$ ?
[qcm]
[option]$3$[/option]
[option]$4$[/option]
[option correct="true"]$5$[/option]
[option]$6$[/option]
[reponse statut="correct"]Bonne réponse !
Dans un graphe non orienté, une boucle compte $2$ fois dans le degré du sommet sur lequel elle est posée. Ici, $3$ arêtes vers d'autres sommets et $2$ pour la boucle, donc le degré vaut $3 + 2 = 5$.[/reponse]
[reponse motif="$3$"]Non.
Cette réponse oublie complètement la boucle. Or chaque boucle contribue au degré du sommet sur lequel elle est attachée.[/reponse]
[reponse motif="$4$"]Non.
Le piège est de compter la boucle comme une seule arête. Dans un graphe non orienté, une boucle est traversée deux fois par le sommet, donc elle pèse $2$ dans le degré.[/reponse]
[reponse motif="$6$"]Non.
Compter une boucle pour $3$ revient à confondre nombre d'arêtes et degré. La règle est : chaque arête vers un autre sommet compte pour $1$, chaque boucle pour $2$.[/reponse]
[reponse statut="incorrect"]Non.
La boucle compte pour $2$ dans le degré. Le total est $3$ arêtes vers d'autres sommets plus $2$ pour la boucle, soit $5$.[/reponse]
[/qcm]
[/etape]

[etape]
Que signifie « les sommets $A$ et $B$ sont adjacents » ?
[qcm]
[option]$A$ et $B$ ont le même degré.[/option]
[option]Il existe une chaîne reliant $A$ à $B$.[/option]
[option correct="true"]$A$ et $B$ sont reliés directement par une arête.[/option]
[option]$A$ et $B$ appartiennent au même cycle.[/option]
[reponse statut="correct"]Tu as raison !
Deux sommets sont adjacents s'il existe une arête (ou un arc) qui les relie directement. Aucun sommet intermédiaire ne s'intercale entre eux.[/reponse]
[reponse motif="$A$ et $B$ ont le même degré."]Non.
Avoir le même degré n'a aucun rapport avec l'adjacence. Deux sommets de degré $3$ peuvent très bien ne partager aucune arête.[/reponse]
[reponse motif="Il existe une chaîne reliant $A$ à $B$."]Non.
Cette propriété signifie que $A$ et $B$ sont dans la même composante connexe, ce qui est plus faible que l'adjacence : une chaîne peut compter plusieurs arêtes intermédiaires.[/reponse]
[reponse motif="$A$ et $B$ appartiennent au même cycle."]Non.
Appartenir à un même cycle n'implique pas être directement reliés par une arête : deux sommets opposés d'un cycle de longueur $4$ ne sont pas adjacents.[/reponse]
[reponse statut="incorrect"]Non.
Deux sommets sont adjacents si et seulement s'ils sont reliés directement par une arête (ou un arc).[/reponse]
[/qcm]
[/etape]

[etape]
À quelle condition un graphe est-il connexe ?
[qcm]
[option]Tous ses sommets ont le même degré.[/option]
[option correct="true"]Deux sommets quelconques peuvent être reliés par une chaîne.[/option]
[option]Il possède au moins une chaîne eulérienne.[/option]
[option]Tous ses sommets sont deux à deux adjacents.[/option]
[reponse statut="correct"]Bravo !
Un graphe est connexe lorsque, pour tout couple de sommets, on peut trouver une chaîne (suite d'arêtes consécutives) qui les relie. Intuitivement, le graphe est en un seul morceau.[/reponse]
[reponse motif="Tous ses sommets ont le même degré."]Non.
Un graphe avec tous les degrés identiques est dit régulier, pas nécessairement connexe : deux triangles disjoints donnent un graphe régulier de degré $2$ qui n'est pas connexe.[/reponse]
[reponse motif="Il possède au moins une chaîne eulérienne."]Non.
Une chaîne eulérienne implique la connexité (sinon impossible de la tracer), mais la réciproque est fausse : beaucoup de graphes connexes n'ont pas de chaîne eulérienne (par exemple s'ils ont 4 sommets de degré impair).[/reponse]
[reponse motif="Tous ses sommets sont deux à deux adjacents."]Non.
Cette propriété définit un graphe complet, pas un graphe simplement connexe. Tout graphe complet est connexe, mais l'inverse n'est pas vrai.[/reponse]
[reponse statut="incorrect"]Non.
La connexité signifie que pour tout couple de sommets, on peut les relier par une chaîne du graphe.[/reponse]
[/qcm]
[/etape]

[etape]
Quelle est la définition de la longueur d'une chaîne ?
[qcm]
[option]Le nombre de sommets distincts visités.[/option]
[option correct="true"]Le nombre d'arêtes parcourues.[/option]
[option]La somme des degrés des sommets visités.[/option]
[option]Le nombre total de sommets dans le graphe.[/option]
[reponse statut="correct"]C'est bien ça !
La longueur d'une chaîne est le nombre d'arêtes qu'elle traverse. Par exemple, la chaîne $(A\,;\,B\,;\,C\,;\,D)$ utilise les arêtes $AB$, $BC$ et $CD$, donc sa longueur vaut $3$.[/reponse]
[reponse motif="Le nombre de sommets distincts visités."]Non.
Pour une chaîne sans sommet répété, le nombre de sommets visités vaut la longueur plus $1$. La longueur compte les arêtes, pas les sommets.[/reponse]
[reponse motif="La somme des degrés des sommets visités."]Non.
Cette quantité n'est pas définie comme une « longueur » pour les chaînes : elle mélange une grandeur locale (le degré) avec un parcours global et n'a pas d'utilité standard.[/reponse]
[reponse motif="Le nombre total de sommets dans le graphe."]Non.
Le nombre total de sommets du graphe est l'ordre du graphe : c'est une caractéristique globale, indépendante de la chaîne considérée.[/reponse]
[reponse statut="incorrect"]Non.
La longueur d'une chaîne est le nombre d'arêtes qui la composent.[/reponse]
[/qcm]
[/etape]

[etape]
Parmi les propositions suivantes, laquelle décrit correctement un cycle dans un graphe ?
[qcm]
[option]Une chaîne dont tous les sommets sont distincts.[/option]
[option]Un sommet relié à lui-même par une arête.[/option]
[option correct="true"]Une chaîne fermée dont toutes les arêtes sont distinctes.[/option]
[option]Une chaîne qui passe par toutes les arêtes du graphe.[/option]
[reponse statut="correct"]Parfait !
Un cycle est une chaîne fermée (l'origine et l'extrémité coïncident) dans laquelle aucune arête n'est utilisée deux fois. Les sommets, eux, peuvent éventuellement se répéter (sauf l'origine et l'extrémité bien sûr).[/reponse]
[reponse motif="Une chaîne dont tous les sommets sont distincts."]Non.
Cette définition correspond à une chaîne élémentaire (ou simple), pas à un cycle. Un cycle, lui, doit revenir à son point de départ.[/reponse]
[reponse motif="Un sommet relié à lui-même par une arête."]Non.
Cette description est celle d'une boucle, qui est une arête particulière, pas une chaîne. Un cycle est un parcours, pas une simple arête.[/reponse]
[reponse motif="Une chaîne qui passe par toutes les arêtes du graphe."]Non.
Cette propriété caractérise une chaîne eulérienne. Un cycle n'a pas besoin de couvrir toutes les arêtes : il suffit qu'il revienne au sommet de départ sans réutiliser d'arête.[/reponse]
[reponse statut="incorrect"]Non.
Un cycle est une chaîne fermée (qui revient au point de départ) dont toutes les arêtes sont distinctes.[/reponse]
[/qcm]
[/etape]