Lycée · Terminale · Maths expertes (option Tle)
Graphes — vocabulaire et propriétés
Sommets, arêtes, chemins, cycles et connexité : les fondamentaux de la théorie des graphes (programme de Maths expertes Tle)
À propos de cette page
Choisis ton niveau. Questions et réponses mélangées à chaque partie. Bonne chance !
Les 36 questions du QCM en version texte
Pour réviser sans écran ou imprimer : chaque question avec ses propositions ; la bonne réponse et son explication se déplient.
Niveau facile — 12 questions
Qu'est-ce qu'un sommet dans un graphe ?
- A. Une arête reliant deux nœuds
- B. Un point du graphe
- C. Le nombre d'arêtes
- D. Un cycle fermé
Réponse
B. Un point du graphe — Un sommet (ou nœud) est l'un des points fondamentaux du graphe.
Qu'est-ce que le degré d'un sommet $v$ ?
- A. Le nombre de sommets du graphe
- B. La longueur du plus court chemin
- C. Le nombre d'arêtes incidentes à $v$
- D. Le nombre de cycles passant par $v$
Réponse
C. Le nombre d'arêtes incidentes à $v$ — Le degré $d(v)$ compte les arêtes reliées à $v$.
Quelle est la somme des degrés dans un graphe à 5 arêtes ?
- A. 5
- B. 10
- C. 15
- D. 25
Réponse
B. 10 — Par le lemme des poignées de mains : $\sum d(v) = 2m = 2 \times 5 = 10$.
Un graphe d'ordre 4 a au maximum combien d'arêtes (graphe simple) ?
- A. 4
- B. 6
- C. 8
- D. 12
Réponse
B. 6 — $K_4$ a $\frac{4 \times 3}{2} = 6$ arêtes.
Qu'est-ce qu'un graphe connexe ?
- A. Un graphe sans cycle
- B. Un graphe où tout sommet a le même degré
- C. Un graphe où tout couple de sommets est relié par une chaîne
- D. Un graphe complet
Réponse
C. Un graphe où tout couple de sommets est relié par une chaîne — La connexité signifie qu'on peut aller de n'importe quel sommet à n'importe quel autre.
Dans un graphe orienté, comment appelle-t-on un arc ?
- A. Une arête bidirectionnelle
- B. Une liaison dirigée entre deux sommets
- C. Un cycle
- D. Une composante connexe
Réponse
B. Une liaison dirigée entre deux sommets — Un arc $(u,v)$ est une liaison dirigée de $u$ vers $v$.
Un arbre à 8 sommets a combien d'arêtes ?
- A. 6
- B. 7
- C. 8
- D. 9
Réponse
B. 7 — Un arbre à $n$ sommets a $n-1$ arêtes : $8-1=7$.
Quel terme désigne un sommet de degré 1 ?
- A. Sommet isolé
- B. Feuille
- C. Racine
- D. Centre
Réponse
B. Feuille — Un sommet de degré 1 est appelé feuille (ou sommet pendant).
Un cycle de longueur 3 dans un graphe non orienté s'appelle aussi :
- A. Un chemin hamiltonien
- B. Un triangle
- C. Une arête
- D. Un sous-graphe biparti
Réponse
B. Un triangle — Un cycle de longueur 3 est un triangle (3 sommets, 3 arêtes).
La longueur d'une chaîne est définie comme :
- A. Le nombre de sommets
- B. Le nombre d'arêtes empruntées
- C. La somme des degrés
- D. Le nombre de cycles
Réponse
B. Le nombre d'arêtes empruntées — La longueur est le nombre d'arêtes dans la chaîne.
Un graphe simple peut-il avoir une boucle (arête d'un sommet vers lui-même) ?
- A. Oui, toujours
- B. Non, par définition
- C. Oui, si tous les degrés sont pairs
- D. Seulement si le graphe est orienté
Réponse
B. Non, par définition — Un graphe simple est sans boucle ni arêtes multiples, par définition.
Dans $K_5$, quel est le degré de chaque sommet ?
- A. 3
- B. 4
- C. 5
- D. 6
Réponse
B. 4 — Dans $K_n$, chaque sommet est relié aux $n-1$ autres : degré $= 5-1 = 4$.
Niveau moyen — 12 questions
Combien d'arêtes a $K_7$ ?
- A. 14
- B. 18
- C. 21
- D. 28
Réponse
C. 21 — $\frac{7 \times 6}{2} = 21$.
Un graphe a 4 sommets de degrés 1, 2, 3, 2. Combien a-t-il d'arêtes ?
- A. 4
- B. 8
- C. 6
- D. 5
Réponse
A. 4 — Somme $= 1+2+3+2=8=2m$, donc $m=4$.
Un graphe est eulérien si et seulement si :
- A. Il est connexe
- B. Tous ses sommets ont un degré pair
- C. Il est connexe et tous ses sommets ont un degré pair
- D. Il n'a pas de cycle
Réponse
C. Il est connexe et tous ses sommets ont un degré pair — Les deux conditions sont nécessaires et suffisantes.
Laquelle des suites suivantes est un cycle dans un graphe $V=\{1,2,3,4\}$, $E=\{\{1,2\},\{2,3\},\{3,4\},\{1,4\}\}$ ?
- A. 1, 2, 3
- B. 1, 2, 3, 4, 1
- C. 1, 2, 1
- D. 2, 3, 4
Réponse
B. 1, 2, 3, 4, 1 — $1-2-3-4-1$ emprunte 4 arêtes présentes et est une chaîne fermée : c'est un cycle.
Qu'est-ce qu'une composante connexe ?
- A. Un sommet isolé
- B. Un sous-graphe connexe maximal
- C. Le plus long cycle du graphe
- D. L'ensemble des arêtes du graphe
Réponse
B. Un sous-graphe connexe maximal — Une composante connexe est un sous-graphe connexe qu'on ne peut pas agrandir en y ajoutant un sommet adjacent.
Un graphe biparti peut-il contenir un cycle de longueur impaire ?
- A. Oui, toujours
- B. Non, jamais
- C. Seulement s'il est complet
- D. Seulement si les deux parties ont le même nombre de sommets
Réponse
B. Non, jamais — Un graphe biparti ne contient que des cycles de longueur paire.
Dans un graphe orienté, $d^+(v) + d^-(v)$ vaut :
- A. Le degré dans le graphe non orienté sous-jacent
- B. Le double du degré
- C. Le nombre d'arcs
- D. Le nombre de sommets
Réponse
A. Le degré dans le graphe non orienté sous-jacent — $d^+(v)+d^-(v)$ est le degré de $v$ dans le graphe non orienté sous-jacent (en remplaçant les arcs par des arêtes).
Le nombre de sommets de degré impair dans un graphe est toujours :
- A. Impair
- B. Pair
- C. Nul
- D. Égal au nombre d'arêtes
Réponse
B. Pair — Conséquence du lemme des poignées de mains : la somme des degrés est paire, donc le nombre de termes impairs est pair.
Un graphe connexe à $n$ sommets et $n-1$ arêtes est nécessairement :
- A. Un graphe complet
- B. Un graphe biparti
- C. Un arbre
- D. Un graphe eulérien
Réponse
C. Un arbre — Un graphe connexe sans cycle est un arbre, et il a exactement $n-1$ arêtes.
Lequel de ces graphes est eulérien ? (Tous ont 4 sommets)
- A. $K_4$
- B. $K_3$ plus un sommet isolé
- C. Un cycle $C_4$
- D. Un chemin $P_4$
Réponse
C. Un cycle $C_4$ — $C_4$ est connexe et tous les sommets ont degré 2 (pair) : il est eulérien.
Dans $K_{3,3}$ (complet biparti), quel est le degré de chaque sommet ?
- A. 2
- B. 3
- C. 4
- D. 6
Réponse
B. 3 — Dans $K_{p,q}$, les sommets d'une partie ont degré $q$ et vice versa. Ici $p=q=3$ : degré 3.
Quelle condition garantit que deux graphes sont isomorphes ?
- A. Ils ont le même nombre de sommets
- B. Ils ont le même nombre de sommets, d'arêtes et des degrés identiques
- C. Il existe une bijection préservant les adjacences
- D. Ils sont tous les deux connexes
Réponse
C. Il existe une bijection préservant les adjacences — L'isomorphisme est une bijection sur les sommets qui préserve les arêtes.
Niveau difficile — 12 questions
Dans un graphe simple à $n$ sommets, si tout sommet a un degré $\ge \frac{n}{2}$, alors le graphe est :
- A. Biparti
- B. Eulérien
- C. Connexe
- D. Un arbre
Réponse
C. Connexe — C'est le théorème de Dirac (1952) : un tel graphe est connexe (et même hamiltonien).
Combien d'arcs a un tournoi à $n$ joueurs (chaque paire joue exactement un match) ?
- A. $n$
- B. $n(n-1)$
- C. $\frac{n(n-1)}{2}$
- D. $n^2$
Réponse
C. $\frac{n(n-1)}{2}$ — Un tournoi est un graphe orienté complet : $\binom{n}{2}=\frac{n(n-1)}{2}$ arcs.
Lequel de ces énoncés sur les arbres est FAUX ?
- A. Un arbre connexe à $n$ sommets a $n-1$ arêtes
- B. Tout arbre est biparti
- C. Un arbre contient exactement un cycle
- D. Un arbre est un graphe acyclique connexe
Réponse
C. Un arbre contient exactement un cycle — Un arbre est précisément un graphe SANS cycle. L'affirmation 'contient exactement un cycle' est fausse.
Un graphe $G$ est connexe et possède un cycle eulérien. Si on ajoute une arête $\{u,v\}$ (déjà reliés), il est encore eulérien si et seulement si :
- A. L'ajout ne crée pas de boucle
- B. $u$ et $v$ avaient un degré impair
- C. $u$ et $v$ avaient un degré pair
- D. L'arête $\{u,v\}$ appartient à un cycle
Réponse
D. L'arête $\{u,v\}$ appartient à un cycle — Ajouter une arête change la parité des degrés de $u$ et $v$. Pour rester eulérien, $u$ et $v$ doivent passer de pair à impair puis à pair — ils devaient donc être pairs, et après ajout ils seraient impairs. Contradiction. En fait l'ajout brise l'eulérien sauf si $u=v$ (boucle, impossible en graphe simple). Réinterprétation : si on ajoute une 2e arête entre $u$ et $v$ (multigraphe), alors $u$ et $v$ ont leur degré qui augmente de 1 : pour que la parité reste paire, ils devaient avoir degré impair. Mais en graphe simple on ne peut pas. La réponse correcte est que c'est impossible dans un graphe simple sans créer un multigraphe.
La chromat... Pour un graphe biparti non vide, le nombre chromatique (minimum de couleurs pour colorier les sommets adjacents en couleurs différentes) est :
- A. 1
- B. 2
- C. 3
- D. 4
Réponse
B. 2 — Tout graphe biparti (non vide et connexe) est 2-colorable : on colorie chaque partie avec une couleur.
Si $G$ est un graphe connexe eulérien, que peut-on dire d'un sous-graphe couvrant (même ensemble de sommets) qui est un arbre ?
- A. Il est aussi eulérien
- B. Il a $|V|-1$ arêtes
- C. Il n'existe pas
- D. Il est 3-régulier
Réponse
B. Il a $|V|-1$ arêtes — Un arbre couvrant d'un graphe à $n$ sommets a toujours $n-1$ arêtes, par définition.
Pour $n \ge 3$, le cycle $C_n$ est eulérien si et seulement si :
- A. $n$ est pair
- B. $n$ est impair
- C. Toujours
- D. Jamais
Réponse
C. Toujours — Dans $C_n$, chaque sommet est de degré 2 (pair) et le graphe est connexe : il est toujours eulérien, quel que soit $n$.
Un graphe $G$ à $n$ sommets et $m$ arêtes vérifie $m \gt \binom{n-1}{2}$. Alors :
- A. $G$ est biparti
- B. $G$ est connexe
- C. $G$ est eulérien
- D. $G$ est un arbre
Réponse
B. $G$ est connexe — Si $m \gt \binom{n-1}{2}$, alors $G$ est connexe (un graphe non connexe a au plus $\binom{n-1}{2}$ arêtes).
Lequel de ces graphes n'est PAS biparti ?
- A. $C_4$
- B. $K_{2,3}$
- C. $C_5$
- D. $P_5$ (chemin de longueur 4)
Réponse
C. $C_5$ — $C_5$ est un cycle de longueur impaire. Un graphe biparti ne peut contenir de cycle impair.
Dans un graphe fortement connexe orienté à $n$ sommets, la somme des demi-degrés extérieurs vaut :
- A. $n$
- B. $n-1$
- C. $|A|$
- D. $\frac{|A|}{2}$
Réponse
C. $|A|$ — $\sum d^+(v) = |A|$ (nombre d'arcs), quelle que soit la structure.
Combien de sommets de degré impair peut avoir un graphe connexe eulérien ?
- A. 0
- B. 2
- C. 4
- D. Toujours un nombre pair
Réponse
A. 0 — Un graphe eulérien (qui admet un cycle eulérien) a TOUS ses sommets de degré pair, donc 0 sommet de degré impair.
Le graphe de Petersen (5 points extérieurs en pentagone + 5 intérieurs en étoile) est-il eulérien ?
- A. Oui, tous les degrés sont pairs
- B. Non, car il n'est pas connexe
- C. Non, car tous les degrés sont impairs (= 3)
- D. Oui, car il est 3-régulier
Réponse
C. Non, car tous les degrés sont impairs (= 3) — Le graphe de Petersen est 3-régulier : tous les sommets ont degré 3 (impair). Il n'est donc pas eulérien.
Cours particuliers de maths expertes (option tle) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs