Lycée · 2ⁿᵈᵉ · Sciences numériques et technologie (SNT)
Graphes et influence
Modéliser les réseaux sociaux par des graphes : sommets, arêtes, degré et propagation de l'information (programme SNT 2nde)
À 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 représentant un réseau social ?
- A. Un lien d'amitié
- B. Un utilisateur ou une entité
- C. Un message envoyé
- D. Un algorithme
Réponse
B. Un utilisateur ou une entité — Dans un graphe de réseau social, chaque sommet représente un utilisateur ou une entité.
Comment s'appelle le lien qui relie deux sommets dans un graphe ?
- A. Un nœud
- B. Un chemin
- C. Une arête
- D. Un degré
Réponse
C. Une arête — Une arête est le lien entre deux sommets dans un graphe.
Quel est le degré d'un sommet ?
- A. Sa distance au sommet le plus proche
- B. Son nombre de voisins directs
- C. La longueur du plus long chemin depuis lui
- D. Son identifiant dans le graphe
Réponse
B. Son nombre de voisins directs — Le degré d'un sommet est le nombre de ses voisins directs (arêtes incidentes).
Dans un graphe non orienté, si A est voisin de B, alors B est voisin de A.
- A. Vrai
- B. Faux
- C. Parfois
- D. Jamais
Réponse
A. Vrai — Dans un graphe non orienté, la relation est symétrique : si A-B est une arête, B-A l'est aussi.
Quel type de graphe modélise le mieux les 'amis' sur Facebook ?
- A. Orienté
- B. Non orienté
- C. Pondéré
- D. Aléatoire
Réponse
B. Non orienté — L'amitié sur Facebook est réciproque : le graphe est non orienté.
Que représente une arête dans un graphe de réseau social ?
- A. Un profil d'utilisateur
- B. Un algorithme de recommandation
- C. Un lien de relation entre deux utilisateurs
- D. Un serveur informatique
Réponse
C. Un lien de relation entre deux utilisateurs — Une arête représente une relation (amitié, abonnement, connexion) entre deux utilisateurs.
Combien d'arêtes comporte un graphe avec 3 sommets tous reliés deux à deux ?
- A. 2
- B. 3
- C. 4
- D. 6
Réponse
B. 3 — 3 sommets tous reliés deux à deux forment 3 arêtes (triangle).
Qu'est-ce qu'un graphe connexe ?
- A. Un graphe sans arêtes
- B. Un graphe où tout sommet est accessible depuis tout autre
- C. Un graphe avec un seul sommet
- D. Un graphe orienté
Réponse
B. Un graphe où tout sommet est accessible depuis tout autre — Un graphe connexe est un graphe dans lequel il existe un chemin entre toute paire de sommets.
Quel terme désigne la longueur du plus court chemin entre deux sommets ?
- A. Diamètre
- B. Degré
- C. Distance
- D. Degré de séparation
Réponse
C. Distance — La distance entre deux sommets est la longueur du plus court chemin les reliant.
Dans la matrice d'adjacence d'un graphe non orienté, que vaut M[i][i] (diagonale) ?
- A. 1
- B. 0
- C. Le degré de i
- D. Indéfini
Réponse
B. 0 — La diagonale vaut 0 : un sommet n'est pas relié à lui-même (pas de boucle).
Qui a proposé la théorie des six degrés de séparation ?
- A. Mark Zuckerberg
- B. Tim Berners-Lee
- C. Stanley Milgram
- D. Alan Turing
Réponse
C. Stanley Milgram — Stanley Milgram a réalisé l'expérience en 1967 montrant que deux personnes sont reliées par au plus 6 intermédiaires.
Quel réseau social utilise des graphes orientés pour les abonnements ?
- A. Facebook
- B. LinkedIn
- C. Twitter/X
- D. Tous les réseaux sociaux
Réponse
C. Twitter/X — Sur Twitter/X, on peut suivre quelqu'un sans être suivi en retour : les liens sont orientés.
Niveau moyen — 12 questions
Un graphe a 5 arêtes. Quelle est la somme de tous les degrés de ses sommets ?
- A. 5
- B. 8
- C. 10
- D. 15
Réponse
C. 10 — La somme des degrés = 2 × nombre d'arêtes = 2 × 5 = 10.
Dans un graphe à 4 sommets {A,B,C,D} avec arêtes A-B, B-C, C-D, A-D, quel est le degré de B ?
- A. 1
- B. 2
- C. 3
- D. 4
Réponse
B. 2 — B est relié à A et C seulement : d(B) = 2.
Quelle est la distance entre A et C dans le graphe : A-B, B-C, A-D, D-C ?
- A. 1
- B. 2
- C. 3
- D. 4
Réponse
B. 2 — Il existe deux chemins de longueur 2 : A-B-C et A-D-C. La distance est 2.
Dans la matrice d'adjacence d'un graphe non orienté, la somme d'une ligne correspond à :
- A. La distance du sommet
- B. Le degré du sommet
- C. Le diamètre du graphe
- D. Le nombre total de sommets
Réponse
B. Le degré du sommet — La somme d'une ligne (ou colonne) de la matrice donne le degré du sommet correspondant.
Un graphe a les arêtes : 1-2, 2-3, 3-4, 4-1. Quel est son diamètre ?
- A. 1
- B. 2
- C. 3
- D. 4
Réponse
B. 2 — Le graphe est un cycle à 4 sommets. La distance maximale entre deux sommets opposés (ex: 1 et 3) est 2.
Comment appelle-t-on un sommet de très grand degré dans un réseau ?
- A. Un cluster
- B. Un hub
- C. Un chemin
- D. Un diamètre
Réponse
B. Un hub — Un hub est un sommet de très grand degré, très bien connecté dans le réseau.
Dans un graphe orienté, si A→B est un arc, cela signifie :
- A. B est ami avec A
- B. A suit B mais B ne suit pas nécessairement A
- C. A et B sont voisins dans les deux sens
- D. A et B ont le même degré
Réponse
B. A suit B mais B ne suit pas nécessairement A — Dans un graphe orienté, A→B signifie que A est lié à B mais pas forcément B à A.
Qu'arrive-t-il à la connexité d'un réseau si on supprime un hub ?
- A. Rien ne change
- B. Le réseau peut se fragmenter en plusieurs parties
- C. Le diamètre diminue
- D. Tous les sommets deviennent isolés
Réponse
B. Le réseau peut se fragmenter en plusieurs parties — Supprimer un hub peut déconnecter le réseau en plusieurs composantes.
Dans un réseau de 6 personnes toutes reliées deux à deux, combien d'arêtes y a-t-il ?
- A. 6
- B. 10
- C. 15
- D. 12
Réponse
C. 15 — Le nombre d'arêtes d'un graphe complet à n sommets est n(n-1)/2 = 6×5/2 = 15.
La propagation d'une information en vagues depuis un sommet ressemble à quel algorithme ?
- A. Tri rapide
- B. Parcours en profondeur
- C. Parcours en largeur (BFS)
- D. Algorithme de Dijkstra
Réponse
C. Parcours en largeur (BFS) — Le parcours en largeur (BFS) explore les voisins couche par couche, comme la propagation par vagues.
Quelle propriété garantit qu'une information peut atteindre tous les utilisateurs d'un réseau ?
- A. Un degré élevé pour tous
- B. La connexité du graphe
- C. Un diamètre maximal
- D. Des arêtes orientées
Réponse
B. La connexité du graphe — Si le graphe est connexe, il existe un chemin entre toute paire de sommets, donc l'information peut atteindre tout le monde.
L'excentricité d'un sommet v est :
- A. Son degré
- B. Sa distance au sommet le plus proche
- C. Sa distance maximale à tout autre sommet
- D. Le nombre de chemins issus de v
Réponse
C. Sa distance maximale à tout autre sommet — L'excentricité de v est la distance maximale entre v et n'importe quel autre sommet du graphe.
Niveau difficile — 12 questions
Un graphe a 6 sommets et est complet (tous reliés deux à deux). Combien d'arêtes comporte-t-il ?
- A. 12
- B. 15
- C. 18
- D. 30
Réponse
B. 15 — Graphe complet à n sommets : n(n-1)/2 = 6×5/2 = 15 arêtes.
Pour un graphe non orienté, quelle relation relie la somme des degrés et le nombre d'arêtes ?
- A. Somme degrés = |A|
- B. Somme degrés = 2|A|
- C. Somme degrés = |S|×|A|
- D. Somme degrés = |A|²
Réponse
B. Somme degrés = 2|A| — Lemme des poignées de mains : chaque arête contribue 2 au total des degrés, donc Σd(v) = 2|A|.
Dans un graphe connexe à n sommets, le nombre minimum d'arêtes est :
- A. n
- B. n-1
- C. n+1
- D. n/2
Réponse
B. n-1 — Un arbre (graphe connexe sans cycle) à n sommets a exactement n-1 arêtes : c'est le minimum pour la connexité.
Quel est le diamètre d'un graphe en forme de chemin (chaîne) à 5 sommets ?
- A. 2
- B. 3
- C. 4
- D. 5
Réponse
C. 4 — Dans une chaîne 1-2-3-4-5, la distance maximale est entre 1 et 5 : diamètre = 4.
Dans la matrice d'adjacence M d'un graphe, que représente M² (produit matriciel) ?
- A. Les distances entre sommets
- B. Le nombre de chemins de longueur 2 entre les sommets
- C. Les degrés au carré
- D. La matrice identité
Réponse
B. Le nombre de chemins de longueur 2 entre les sommets — M²[i][j] donne le nombre de chemins de longueur exactement 2 entre les sommets i et j.
Quelle propriété des réseaux sociaux réels explique le phénomène des petits mondes ?
- A. Beaucoup de sommets isolés
- B. Présence de hubs et forte densité locale
- C. Diamètre très grand
- D. Peu de connexions
Réponse
B. Présence de hubs et forte densité locale — Les réseaux petits mondes combinent une forte densité locale et des hubs qui servent de raccourcis globaux.
Si le degré de séparation moyen sur un réseau est de 4, combien d'étapes faut-il au maximum pour atteindre n'importe qui (en moyenne) ?
- A. 2
- B. 4
- C. 8
- D. 16
Réponse
B. 4 — Le degré de séparation moyen de 4 signifie que 4 étapes (intermédiaires) suffisent en moyenne.
Pourquoi une fausse information se propage-t-elle parfois plus vite qu'une vraie ?
- A. Car les graphes orientés sont plus rapides
- B. Car les algorithmes la pénalisent
- C. Car elle génère plus de partages, augmentant la propagation
- D. Car elle a toujours moins de sommets
Réponse
C. Car elle génère plus de partages, augmentant la propagation — Les fausses informations sont souvent plus émotionnelles et génèrent plus d'interactions, augmentant leur vitesse de propagation.
Dans un réseau orienté, la notion équivalente au degré pour les abonnés est :
- A. Le degré sortant
- B. Le degré entrant
- C. L'excentricité
- D. Le diamètre
Réponse
B. Le degré entrant — Le degré entrant (in-degree) d'un sommet est le nombre d'arcs qui pointent vers lui = nombre d'abonnés.
Deux graphes ont le même nombre de sommets et d'arêtes. Sont-ils nécessairement identiques ?
- A. Oui
- B. Non, la structure peut être différente
- C. Oui, si connexes
- D. Oui, si non orientés
Réponse
B. Non, la structure peut être différente — Deux graphes peuvent avoir même |S| et |A| mais des connexions totalement différentes.
Quelle technique permet de trouver le plus court chemin dans un graphe non pondéré ?
- A. Tri à bulles
- B. Parcours en profondeur
- C. Parcours en largeur (BFS)
- D. Récursion
Réponse
C. Parcours en largeur (BFS) — Le BFS (Breadth First Search) trouve automatiquement les plus courts chemins dans un graphe non pondéré.
Dans un réseau social, deux personnes ont un ami en commun. Quelle est leur distance dans le graphe ?
- A. 1
- B. 2
- C. 3
- D. 4
Réponse
B. 2 — Un ami en commun = un intermédiaire = chemin de longueur 2 entre les deux personnes.
Cours particuliers de sciences numériques et technologie (snt) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.
Soutien scolaire à Marseille · Cours particuliers au lycée · Aide aux devoirs