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
Sans document · Les réponses doivent être rédigées et justifiées. Soigne l'orthographe et la présentation.
Devoir surveillé de fin de chapitre, tout en niveau difficile. Travaille seul et sans aide, puis vérifie tes réponses avec le corrigé détaillé dépliable en bas de page.
Exercice 1 — Vocabulaire et représentation des graphes
/ 4 pts- Définir les termes suivants : sommet, arête, degré, graphe connexe. (1 pt par définition)
- Dessiner un graphe non orienté à 4 sommets {A, B, C, D} avec arêtes A-B, A-C, B-D, C-D. Indiquer le degré de chaque sommet. (0 pt de dessin ; 1 pt pour les 4 degrés corrects)
Exercice 2 — Distances et diamètre
/ 5 pts- Soit le graphe à 5 sommets {P, Q, R, S, T} avec arêtes : P-Q, P-R, Q-S, R-S, S-T.
a) Donner la distance entre P et T. Justifier en indiquant le chemin. (2 pts)
b) Donner la distance entre Q et T. (1 pt)
c) Calculer le diamètre de ce graphe. (2 pts)
Exercice 3 — Matrice d'adjacence
/ 5 pts- On donne le graphe non orienté à 4 sommets {1, 2, 3, 4} avec arêtes : 1-2, 1-4, 2-3, 3-4.
a) Écrire la matrice d'adjacence $M$ de ce graphe. (2 pts)
b) Calculer le degré de chaque sommet à partir de la matrice. (2 pts)
c) Ce graphe est-il connexe ? Justifier. (1 pt)
Exercice 4 — Propagation de l'information
/ 4 pts- Un réseau social compte 6 utilisateurs : M1, M2, M3, M4, M5, M6. Les liens sont : M1-M2, M1-M3, M2-M4, M3-M4, M4-M5, M4-M6.
a) Quel est le sommet le plus influent (degré le plus élevé) ? (1 pt)
b) M1 publie une information. En combien d'étapes M5 la reçoit-il (au minimum) ? Donner le chemin. (2 pts)
c) Si M4 quitte le réseau, M5 et M6 peuvent-ils recevoir l'information de M1 ? Justifier. (1 pt)
Exercice 5 — Petits mondes et enjeux des réseaux sociaux
/ 2 pts- Expliquer en quelques lignes ce qu'est la théorie des petits mondes et son lien avec les réseaux sociaux numériques. (1 pt)
b) Donner un avantage et un inconvénient du faible degré de séparation dans les réseaux sociaux. (1 pt)
Corrigé détaillé — à n'ouvrir qu'après avoir rendu la copie
Exercice 1 — Vocabulaire et représentation des graphes
Corrigé :
Sommet : nœud du graphe, représente un élément (utilisateur, ville…).
Arête : lien entre deux sommets, représente une relation.
Degré : nombre de voisins directs d'un sommet.
Graphe connexe : graphe dans lequel tout sommet est accessible depuis tout autre sommet.
Degrés : d(A) = 2 (relié à B et C), d(B) = 2 (relié à A et D), d(C) = 2 (relié à A et D), d(D) = 2 (relié à B et C).
Vérification : somme des degrés = 2+2+2+2 = 8 = 2×4 arêtes. ✓
Exercice 2 — Distances et diamètre
Corrigé :
a) Chemin le plus court P → R → S → T (longueur 3) ou P → Q → S → T (longueur 3). Distance d(P, T) = 3.
b) Chemin Q → S → T (longueur 2). Distance d(Q, T) = 2.
c) Calcul de toutes les distances :
d(P,Q)=1, d(P,R)=1, d(P,S)=2, d(P,T)=3
d(Q,R)=2, d(Q,S)=1, d(Q,T)=2
d(R,S)=1, d(R,T)=2
d(S,T)=1
La distance maximale est 3 (entre P et T). Diamètre = 3.
Exercice 3 — Matrice d'adjacence
Corrigé :
a) Matrice :
$M = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$
b) d(1) = somme ligne 1 = 0+1+0+1 = 2 ; d(2) = 1+0+1+0 = 2 ; d(3) = 0+1+0+1 = 2 ; d(4) = 1+0+1+0 = 2.
Vérification : somme totale = 8 = 2×4 arêtes. ✓
c) Oui, le graphe est connexe : depuis chaque sommet on peut atteindre tous les autres (ex: chemin 1-2-3-4).
Exercice 4 — Propagation de l'information
Corrigé :
a) d(M1) = 2, d(M2) = 2, d(M3) = 2, d(M4) = 4 (relié à M2, M3, M5, M6). Le sommet M4 est le plus influent.
b) Chemins depuis M1 vers M5 : M1-M2-M4-M5 (3 étapes) ou M1-M3-M4-M5 (3 étapes). Distance minimale = 3 étapes.
c) Non. Sans M4, M5 et M6 sont isolés du reste du réseau (ils n'ont pas d'autre connexion). M1 ne peut plus les atteindre : le graphe n'est plus connexe.
Exercice 5 — Petits mondes et enjeux des réseaux sociaux
Corrigé :
a) La théorie des petits mondes (Milgram, 1967) postule que deux personnes quelconques sont reliées par au plus 6 intermédiaires. Dans les réseaux sociaux numériques, ce nombre est encore plus faible (3,57 sur Facebook en 2016) car les graphes ont de nombreux hubs et une forte densité locale, créant des raccourcis qui réduisent les distances.
b) Avantage : l'information utile (informations de santé, alertes…) se propage très rapidement. Inconvénient : les fausses informations (fake news) et les contenus nuisibles se propagent aussi très vite, touchant des millions de personnes en quelques heures.
Ce contrôle de sciences numériques et technologie (snt) 2ⁿᵈᵉ en bref
Un devoir surveillé type contrôle en classe sur « Graphes et influence » : 5 exercices, 60 minutes, noté sur 20. Le corrigé détaillé est dépliable sous le sujet.
- Exercice 1 — Vocabulaire et représentation des graphes/ 4 pts
- Exercice 2 — Distances et diamètre/ 5 pts
- Exercice 3 — Matrice d'adjacence/ 5 pts
- Exercice 4 — Propagation de l'information/ 4 pts
- Exercice 5 — Petits mondes et enjeux des réseaux sociaux/ 2 pts
Notions évaluées
Qu'est-ce qu'un graphe ?, Vocabulaire des graphes, Degré d'un sommet et influence, Chemins et distances, Matrice d'adjacence, Modéliser un réseau social.
Pour préparer ce contrôle
- Relire le cours.
- Refaire les exercices corrigés et les problèmes.
- Se tester avec le QCM (36 questions).
- Faire ce sujet en conditions réelles — 60 min, sans le cours — puis se corriger et noter les points à revoir.
Voir tous les contrôles de sciences numériques et technologie (snt) 2ⁿᵈᵉ · tous les devoirs surveillés corrigés
Questions fréquentes sur ce sujet
- Combien de temps dure ce contrôle sur « Graphes et influence » ?
- 60 minutes pour 5 exercices notés sur 20. Prévois le double si tu enchaînes avec la correction.
- Le corrigé est-il fourni ?
- Oui : le corrigé détaillé se déplie sous le sujet, à n'ouvrir qu'après avoir rendu la copie.
- Ce sujet peut-il servir de DS, de contrôle ou d'interrogation ?
- Oui : c'est un devoir surveillé complet de 60 minutes. Pour une interrogation courte, garde un ou deux exercices ; pour un DS ou un contrôle de fin de chapitre, fais le sujet entier en temps limité.
- Ce sujet suit-il le programme de sciences numériques et technologie (snt) de seconde ?
- Oui : il évalue uniquement les notions du chapitre « Graphes et influence » du programme officiel de sciences numériques et technologie (snt) en seconde, soit Qu'est-ce qu'un graphe ?, Vocabulaire des graphes, Degré d'un sommet et influence, Chemins et distances.
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