Ressources · 2ⁿᵈᵉ · Sciences numériques et technologie (SNT)
Graphes et influence
Modéliser un réseau social : sommets, arêtes, degré, distance, diamètre, centre, rayon, petit monde (SNT de 2nde)
À propos de cette page
Choisis ton niveau. Questions et réponses mélangées à chaque partie. Bonne chance !
Les 24 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 — 8 questions
Dans le graphe d'un réseau social d'amitié, un sommet représente…
- A. une relation d'amitié
- B. un utilisateur
- C. un message publié
- D. un groupe d'amis
Réponse
B. un utilisateur — Les sommets sont les utilisateurs ; les relations d'amitié sont les arêtes.
Le degré d'un sommet est…
- A. sa plus grande distance aux autres
- B. le nombre de chaînes qui en partent
- C. le nombre total de sommets
- D. le nombre de ses voisins
Réponse
D. le nombre de ses voisins — Le degré compte les voisins, c'est-à-dire les arêtes issues du sommet. La plus grande distance aux autres est l'excentricité.
Un graphe est dit orienté quand…
- A. chaque lien a un sens (A suit B)
- B. tous les sommets ont le même degré
- C. il contient au moins un triangle
- D. il n'a qu'un seul sommet central
Réponse
A. chaque lien a un sens (A suit B) — Dans un graphe orienté, chaque lien est une flèche : c'est le cas d'un réseau d'abonnements.
La distance entre deux sommets d'un graphe connexe est…
- A. le nombre total d'arêtes que contient le graphe
- B. la somme de leurs deux degrés
- C. la longueur d'une plus courte chaîne
- D. le nombre de leurs voisins communs
Réponse
C. la longueur d'une plus courte chaîne — La distance est le nombre d'arêtes d'une plus courte chaîne reliant les deux sommets.
Le diamètre d'un graphe connexe est…
- A. la plus petite excentricité
- B. le plus grand degré
- C. la plus grande distance entre deux sommets
- D. le nombre de sommets moins un
Réponse
C. la plus grande distance entre deux sommets — Le diamètre est la plus grande excentricité, donc la plus grande distance entre deux sommets. La plus petite excentricité est le rayon.
L'expérience de Milgram (1967) consistait à…
- A. faire suivre une lettre à un inconnu via des connaissances
- B. compter les amis en ligne d'un grand groupe d'étudiants américains
- C. mesurer le temps passé chaque jour sur les réseaux
- D. cartographier le réseau téléphonique
Réponse
A. faire suivre une lettre à un inconnu via des connaissances — Chaque participant transmettait la lettre à une connaissance personnelle, jusqu'au destinataire inconnu. Internet n'existait pas encore.
Le centre d'un graphe est formé du ou des sommets…
- A. de plus grand degré
- B. d'excentricité maximale
- C. reliés à tous les autres
- D. d'excentricité minimale
Réponse
D. d'excentricité minimale — Le centre regroupe les sommets dont l'excentricité est égale au rayon, c'est-à-dire minimale.
Dans une liste d'adjacence, on écrit pour chaque sommet…
- A. son degré seulement
- B. la liste de ses voisins
- C. sa distance au centre
- D. la liste de toutes les arêtes
Réponse
B. la liste de ses voisins — Une liste d'adjacence associe à chaque sommet la liste de ses voisins ; le degré est la longueur de cette liste.
Niveau moyen — 8 questions
Un graphe non orienté possède 9 arêtes. La somme des degrés de ses sommets vaut…
- A. 9
- B. 18
- C. 4,5
- D. on ne peut pas savoir
Réponse
B. 18 — La somme des degrés est le double du nombre d'arêtes : 2 × 9 = 18.
Graphe : A–B, B–C, C–D, D–E (une chaîne de cinq sommets). Son diamètre vaut…
- A. 5
- B. 3
- C. 4
- D. 2
Réponse
C. 4 — La plus grande distance est d(A, E) : 4 arêtes. Attention à ne pas compter les sommets.
Un sommet central est relié à 7 autres sommets, qui ne sont reliés à rien d'autre. Le rayon de ce graphe vaut…
- A. 1
- B. 2
- C. 7
- D. 8
Réponse
A. 1 — Le sommet central est à distance 1 de tous les autres : son excentricité vaut 1, c'est la plus petite.
Graphe : X–Y, Y–Z, Z–X (un triangle) et W relié uniquement à X. L'excentricité de W vaut…
- A. 1
- B. 3
- C. 4
- D. 2
Réponse
D. 2 — d(W, X) = 1, d(W, Y) = d(W, Z) = 2 (en passant par X). La plus grande distance est 2.
amis = {'Tom': ['Ugo', 'Val'], 'Ugo': ['Tom'], 'Val': ['Tom']}. Que vaut len(amis['Tom']) ?
- A. 2
- B. 3
- C. 1
- D. 0
Réponse
A. 2 — amis['Tom'] est la liste ['Ugo', 'Val'], qui contient 2 éléments : Tom a 2 amis.
Dix sommets forment un anneau : chacun est relié à ses deux voisins de l'anneau. Le diamètre vaut…
- A. 10
- B. 5
- C. 9
- D. 4
Réponse
B. 5 — Le sommet le plus éloigné est le sommet opposé : 5 arêtes dans un sens comme dans l'autre.
Dans un réseau d'abonnements, 5 comptes suivent @sol et @sol suit 2 comptes. Combien @sol a-t-il d'abonnés ?
- A. 2
- B. 7
- C. 5
- D. 3
Réponse
C. 5 — Les abonnés sont les comptes qui suivent @sol (flèches entrantes) : 5. Les 2 comptes suivis sont ses abonnements.
Chaîne A–B–C–D–E–F–G (sept sommets). Le centre de ce graphe est…
- A. A et G
- B. C, D et E
- C. tous les sommets
- D. D seul
Réponse
D. D seul — e(D) = 3, alors que e(C) = e(E) = 4 et e(A) = e(G) = 6. Seul D a l'excentricité minimale.
Niveau difficile — 8 questions
Un graphe est formé de deux groupes de sommets sans aucune arête entre eux. Son diamètre…
- A. vaut 0
- B. est égal au nombre de groupes
- C. n'est pas défini
- D. est la somme des diamètres des deux groupes
Réponse
C. n'est pas défini — Le graphe n'est pas connexe : la distance entre deux sommets de groupes différents n'existe pas, donc le diamètre n'est pas défini.
Le sommet de plus grand degré fait-il toujours partie du centre ?
- A. oui, toujours
- B. oui, dès que le graphe est connexe
- C. non, jamais
- D. non, pas nécessairement
Réponse
D. non, pas nécessairement — Un sommet très connecté situé en bout de réseau (par exemple relié à plusieurs feuilles et au reste par une longue chaîne) peut avoir une grande excentricité. Le centre dépend des distances.
Pourquoi les « six degrés » de Milgram ne sont-ils qu'un ordre de grandeur ?
- A. beaucoup de lettres ne sont jamais arrivées
- B. les participants connaissaient tous bien la cible
- C. les lettres passaient par la poste aérienne
- D. la cible habitait dans le même quartier
Réponse
A. beaucoup de lettres ne sont jamais arrivées — Seule une minorité des lettres est arrivée, et les participants ne trouvaient pas forcément le plus court chemin : le résultat est une estimation.
Une chaîne de longueur 5 relie A à B. On peut affirmer que…
- A. d(A, B) = 5
- B. d(A, B) ≤ 5
- C. d(A, B) ≥ 5
- D. d(A, B) > 5
Réponse
B. d(A, B) ≤ 5 — La distance est la longueur d'une plus courte chaîne : elle est au plus 5, mais une chaîne plus courte peut exister.
Ajouter une arête à un graphe connexe…
- A. diminue forcément le diamètre d'au moins 1
- B. ne peut pas augmenter le diamètre
- C. augmente toujours le rayon
- D. ne change jamais aucune distance
Réponse
B. ne peut pas augmenter le diamètre — Une arête de plus ne peut que créer des raccourcis : les distances diminuent ou restent égales. Le diamètre peut rester le même.
Graphe orienté : A suit B et B suit C, sans autre lien. En respectant le sens des flèches, la distance de C à A est…
- A. 2
- B. 1
- C. aucun chemin : non définie
- D. 0
Réponse
C. aucun chemin : non définie — Aucune flèche ne part de C : il n'existe pas de chemin de C vers A. La distance de A à C, elle, vaut 2.
Léa ne voit que les publications partagées par les comptes qu'elle suit. Quelle affirmation est correcte ?
- A. ce qu'elle voit dépend de qui elle suit
- B. elle voit toutes les publications du réseau
- C. elle voit d'abord les comptes les plus anciens
- D. ses abonnés décident de ce qu'elle voit
Réponse
A. ce qu'elle voit dépend de qui elle suit — Son fil est conditionné par le choix préalable de ses abonnements ; ses abonnés, eux, n'influencent pas ce qu'elle voit.
Dans un graphe non orienté, un élève trouve une somme des degrés égale à 15. On en déduit que…
- A. le graphe a 7,5 arêtes
- B. le graphe a 15 arêtes
- C. le graphe a 30 arêtes
- D. c'est impossible
Réponse
D. c'est impossible — La somme des degrés vaut le double du nombre d'arêtes, elle est donc toujours paire : 15 révèle une erreur de comptage.
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.
Soutien scolaire à Marseille · Cours particuliers au lycée · Aide aux devoirs