Ressources · Terminale · Maths expertes (option Tle)
Vocabulaire et propriétés
Graphes : sommets, arêtes, ordre, sommets adjacents, graphe complet ; degré et lemme des poignées de main ; graphes orientés, chemins et circuits ; chaînes, cycles et connexité ; chaînes et cycles eulériens, théorème d’Euler.
À propos de cette page
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
Dans un graphe, l’ordre désigne :
- A. le nombre d’arêtes du graphe
- B. le nombre de sommets du graphe
- C. le plus grand degré d’un sommet
- D. la longueur de la plus longue chaîne
Réponse
B. le nombre de sommets du graphe — Par définition, l’ordre est le nombre de sommets. Le nombre d’arêtes est une autre donnée, reliée aux degrés par le lemme des poignées de main.
Le degré d’un sommet est :
- A. le nombre d’arêtes incidentes à ce sommet
- B. le nombre total de sommets du graphe
- C. le nombre de chaînes partant de ce sommet
- D. le nombre de cycles passant par lui
Réponse
A. le nombre d’arêtes incidentes à ce sommet — Le degré compte les arêtes dont le sommet est une extrémité, une boucle comptant pour 2. Dans un graphe simple, c’est le nombre de voisins.
Un graphe est connexe lorsque :
- A. tous ses sommets ont le même degré
- B. il possède au moins un cycle
- C. tous ses sommets sont de degré pair
- D. deux sommets quelconques sont reliés par une chaîne
Réponse
D. deux sommets quelconques sont reliés par une chaîne — C’est la définition. Avoir des degrés égaux ou pairs ne dit rien de la connexité : deux triangles séparés ont tous leurs degrés égaux à 2.
La somme des degrés des sommets d’un graphe est toujours égale :
- A. au nombre d’arêtes
- B. au double du nombre de sommets
- C. au double du nombre d’arêtes
- D. au nombre de sommets
Réponse
C. au double du nombre d’arêtes — C’est le lemme des poignées de main : chaque arête est comptée deux fois, une fois à chacune de ses extrémités.
Dans un graphe orienté, une liaison entre deux sommets s’appelle :
- A. un arc
- B. une boucle orientée
- C. une chaîne
- D. une arête simple
Réponse
A. un arc — Les liaisons d’un graphe orienté sont des arcs : l’arc A → B se parcourt de A vers B seulement.
La longueur d’une chaîne est :
- A. le nombre de sommets qu’elle contient
- B. le nombre de sommets distincts rencontrés
- C. le nombre d’arêtes qu’elle emprunte
- D. le nombre de cycles qu’elle contient
Réponse
C. le nombre d’arêtes qu’elle emprunte — On compte les arêtes, pas les sommets : une chaîne de quatre sommets consécutifs a pour longueur 3.
Le graphe complet K₁₃ possède :
- A. 78 arêtes
- B. 156 arêtes
- C. 169 arêtes
- D. 13 arêtes
Réponse
A. 78 arêtes — K₁₃ a 13 × 12 / 2 = 78 arêtes : une par paire de sommets. 156 compte chaque arête deux fois, et 169 = 13² n’a pas de sens ici.
Un sommet porte une boucle et deux autres arêtes. Son degré vaut :
- A. 2
- B. 3
- C. 5
- D. 4
Réponse
D. 4 — Une boucle compte pour 2 dans le degré, et chacune des deux autres arêtes pour 1 : le degré vaut 4.
Un cycle eulérien est une chaîne fermée qui :
- A. passe une fois et une seule par chaque sommet
- B. emprunte chaque arête une fois et une seule
- C. emprunte deux fois chaque arête du graphe
- D. passe par tous les sommets de degré pair
Réponse
B. emprunte chaque arête une fois et une seule — Eulérien porte sur les arêtes : chacune est empruntée exactement une fois. La chaîne peut repasser plusieurs fois par un même sommet.
Dans un graphe orienté, la somme des degrés sortants est égale :
- A. au double du nombre d’arcs
- B. à la somme des degrés pairs
- C. au nombre de sommets
- D. au nombre d’arcs du graphe
Réponse
D. au nombre d’arcs du graphe — Chaque arc part d’un seul sommet : il est compté une fois dans les degrés sortants. Il en va de même pour les degrés entrants.
Dans un graphe simple d’ordre 8, le degré d’un sommet vaut au plus :
- A. 8
- B. 7
- C. 16
- D. 28
Réponse
B. 7 — Sans boucle ni arête multiple, un sommet a au plus un voisin parmi chacun des 7 autres sommets.
Dans le graphe d’arêtes A–B, B–C, C–D, D–B et D–E, le degré de D vaut :
- A. 2
- B. 4
- C. 3
- D. 1
Réponse
C. 3 — D est extrémité de C–D, D–B et D–E : il a 3 voisins, donc d(D) = 3.
Niveau moyen ★★ — 12 questions
Un graphe a 9 sommets, tous de degré 4. Son nombre d’arêtes est :
- A. 36
- B. 13
- C. 9
- D. 18
Réponse
D. 18 — La somme des degrés vaut 9 × 4 = 36, et le lemme des poignées de main donne 36 = 2m, soit m = 18.
Un graphe connexe dont tous les sommets sont de degré pair admet :
- A. un cycle eulérien
- B. une chaîne eulérienne non fermée
- C. un cycle passant une fois par chaque sommet
- D. aucune chaîne eulérienne
Réponse
A. un cycle eulérien — C’est le théorème d’Euler : connexe et tous les degrés pairs, le graphe admet un cycle eulérien.
Un graphe connexe a exactement deux sommets de degré impair, P et Q. Il admet :
- A. un cycle eulérien qui passe par P
- B. une chaîne eulérienne d’extrémités P et Q
- C. une chaîne eulérienne fermée en P
- D. aucune chaîne eulérienne possible
Réponse
B. une chaîne eulérienne d’extrémités P et Q — Le théorème d’Euler garantit une chaîne eulérienne non fermée, et ses extrémités sont les deux sommets de degré impair.
Dans un graphe orienté qui comporte 12 arcs, la somme des degrés entrants vaut :
- A. 6
- B. 24
- C. 12
- D. on ne peut pas la calculer
Réponse
C. 12 — Chaque arc arrive en un seul sommet : la somme des degrés entrants est le nombre d’arcs, 12.
Un graphe d’ordre 6 dont les degrés seraient 5, 4, 3, 3, 2 et 2 :
- A. a 19 arêtes
- B. n’existe pas
- C. a 9 arêtes et demie
- D. est un graphe complet
Réponse
B. n’existe pas — La somme des degrés vaut 19, impaire ; or elle doit être égale à 2m. Un tel graphe n’existe pas.
Dans le graphe d’arêtes P–Q, Q–R, R–S, S–T et T–P, la plus courte chaîne de P à S a pour longueur :
- A. 1
- B. 3
- C. 4
- D. 2
Réponse
D. 2 — P–T–S emprunte deux arêtes ; P et S ne sont pas adjacents, donc on ne peut pas faire mieux. L’autre chaîne, P–Q–R–S, est de longueur 3.
Le graphe de sommets 1, 2, 3, 4, 5, 6 et d’arêtes 1–2, 3–4 et 4–5 a :
- A. 3 composantes connexes
- B. 2 composantes connexes
- C. 4 composantes connexes
- D. 6 composantes connexes
Réponse
A. 3 composantes connexes — Les composantes sont {1, 2}, {3, 4, 5} et {6} : le sommet 6, isolé, forme à lui seul une composante.
Un graphe connexe a quatre sommets de degré impair. Alors :
- A. il admet un cycle eulérien
- B. il admet une chaîne eulérienne
- C. il n’a ni cycle ni chaîne eulérienne
- D. il n’est pas un graphe simple
Réponse
C. il n’a ni cycle ni chaîne eulérienne — Le théorème d’Euler demande 0 sommet impair (cycle) ou exactement 2 (chaîne non fermée) : avec 4, ni l’un ni l’autre.
Une chaîne passe par 6 sommets, tous distincts. Sa longueur est :
- A. 6
- B. 5
- C. 7
- D. 12
Réponse
B. 5 — Entre 6 sommets consécutifs, il y a 5 arêtes : la longueur est 5.
Le graphe complet K₁₁ :
- A. admet un cycle eulérien de longueur 55
- B. admet une chaîne eulérienne non fermée
- C. n’admet aucune chaîne eulérienne
- D. admet un cycle eulérien de longueur 11
Réponse
A. admet un cycle eulérien de longueur 55 — K₁₁ est connexe et ses sommets sont de degré 10, pair : il admet un cycle eulérien, dont la longueur est le nombre d’arêtes, 11 × 10 / 2 = 55.
Dans un graphe orienté, un sommet a un degré sortant nul. Alors :
- A. aucun chemin n’arrive à ce sommet
- B. ce sommet porte une boucle
- C. aucun chemin ne part de ce sommet
- D. le graphe n’a aucun circuit
Réponse
C. aucun chemin ne part de ce sommet — Aucun arc ne part de ce sommet, donc aucun chemin de longueur non nulle ne peut en partir. Des arcs peuvent y arriver, et le reste du graphe peut contenir des circuits.
On ajoute une arête entre deux sommets de degré impair. Le nombre de sommets de degré impair :
- A. augmente de 2
- B. ne change pas
- C. diminue de 1
- D. diminue de 2
Réponse
D. diminue de 2 — L’arête ajoute 1 au degré de ses deux extrémités : les deux sommets impairs deviennent pairs, les autres ne changent pas.
Niveau difficile ★★★ — 12 questions
« Tous les degrés sont pairs, donc il y a un cycle eulérien » : quelle hypothèse manque ?
- A. que le graphe soit complet
- B. que le nombre d’arêtes soit pair
- C. que l’ordre du graphe soit pair
- D. que le graphe soit connexe
Réponse
D. que le graphe soit connexe — Le théorème d’Euler suppose la connexité. Deux triangles séparés ont tous leurs degrés pairs et aucun cycle eulérien.
Existe-t-il un graphe d’ordre 11 dont tous les sommets sont de degré 5 ?
- A. oui, il possède 55 arêtes
- B. non, la somme des degrés serait impaire
- C. oui, il possède 27 arêtes
- D. non, un degré dépasse au plus 4
Réponse
B. non, la somme des degrés serait impaire — La somme des degrés vaudrait 11 × 5 = 55, impaire : impossible, puisqu’elle doit valoir 2m.
Dans tout graphe simple d’ordre n ⩾ 2 :
- A. deux sommets au moins ont le même degré
- B. les degrés sont deux à deux distincts
- C. un sommet est toujours de degré n − 1
- D. un sommet est toujours de degré 0
Réponse
A. deux sommets au moins ont le même degré — Les degrés vont de 0 à n − 1, mais 0 et n − 1 ne peuvent pas être pris ensemble : au plus n − 1 valeurs pour n sommets, donc deux degrés égaux.
Un graphe est formé de deux cycles de longueur 4, sans arête entre eux. Alors :
- A. il admet un cycle eulérien de longueur 8
- B. il est connexe puisque chaque cycle l’est
- C. il a une chaîne eulérienne de longueur 8
- D. il n’a ni cycle eulérien ni chaîne eulérienne
Réponse
D. il n’a ni cycle eulérien ni chaîne eulérienne — Les deux cycles forment deux composantes connexes : aucune chaîne ne passe de l’un à l’autre, donc aucune chaîne ne peut emprunter les 8 arêtes.
Un graphe connexe a 12 arêtes et exactement deux sommets de degré impair, P et Q. Toute chaîne eulérienne :
- A. est fermée et de longueur 12
- B. a pour extrémités P et Q et pour longueur 12
- C. a pour extrémités P et Q et pour longueur 11
- D. passe une fois par chaque sommet
Réponse
B. a pour extrémités P et Q et pour longueur 12 — Ses extrémités sont les deux sommets impairs, et elle emprunte chacune des 12 arêtes une fois : sa longueur est 12.
Un graphe simple d’ordre 5 de degrés 4, 4, 2, 1 et 1 :
- A. existe et a 6 arêtes
- B. existe et a 12 arêtes
- C. n’existe pas, bien que la somme soit paire
- D. n’existe pas, car la somme est impaire
Réponse
C. n’existe pas, bien que la somme soit paire — La somme vaut 12, paire. Mais les deux sommets de degré 4 seraient voisins de tous les autres, et les trois derniers auraient alors au moins deux voisins chacun.
Dans un graphe orienté fini, chaque sommet a un degré sortant au moins égal à 1. Alors le graphe :
- A. contient au moins un circuit
- B. est forcément complet
- C. a tous ses degrés entrants égaux à 1
- D. ne contient aucun circuit
Réponse
A. contient au moins un circuit — En suivant des arcs sortants, on revient forcément sur un sommet déjà rencontré, car il n’y en a qu’un nombre fini : la portion parcourue entre deux passages est un circuit.
Un graphe connexe a 6 sommets de degré impair. Pour obtenir un cycle eulérien en ajoutant des arêtes, il en faut au moins :
- A. 6
- B. 2
- C. 3
- D. 1
Réponse
C. 3 — Chaque arête ajoutée rend pairs au plus deux sommets impairs : il en faut au moins 6 / 2 = 3.
Une chaîne eulérienne va de P à Q. Un sommet S, différent de P et de Q, est de degré 6. La chaîne traverse S :
- A. 6 fois
- B. 2 fois
- C. 1 fois
- D. 3 fois
Réponse
D. 3 fois — À chaque traversée, la chaîne utilise deux arêtes de S, une pour arriver et une pour repartir ; les 6 arêtes sont toutes empruntées une fois, d’où 6 / 2 = 3 traversées.
Les sommets sont les entiers de 1 à 10 ; deux entiers sont adjacents lorsque leur somme est impaire. Le nombre d’arêtes est :
- A. 45
- B. 25
- C. 50
- D. 20
Réponse
B. 25 — Une somme est impaire lorsqu’un entier est pair et l’autre impair : 5 choix pour l’entier impair et 5 pour l’entier pair, soit 5 × 5 = 25 arêtes.
Un graphe de 12 sommets a 4 composantes connexes. Pour le rendre connexe, il faut ajouter au moins :
- A. 1 arête
- B. 4 arêtes
- C. 3 arêtes
- D. 11 arêtes
Réponse
C. 3 arêtes — Chaque arête ajoutée réunit au plus deux composantes : pour passer de 4 composantes à 1, il en faut au moins 3, et trois bien choisies suffisent.
Un graphe a 7 sommets, dont exactement 3 de degré impair. Alors :
- A. il admet une chaîne eulérienne
- B. il a 3 composantes connexes
- C. un tel graphe n’existe pas
- D. il a exactement 7 arêtes
Réponse
C. un tel graphe n’existe pas — Le nombre de sommets de degré impair est toujours pair, conséquence du lemme des poignées de main : 3 est impossible.
Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs